Masala #XWHBIND7NM

Xotira 128 MB Vaqt 1000 ms
14

Transport

Dadorlandtiria mamlakatida (N+1)(N + 1)ta shahar bor va ular 1 dan (N+1)(N + 1)gacha raqamlangan.Shuningdek, mamlakatda 4 xil transport turi bor: avtobus, taksi, poyezd, samolyot.Sizga o’lchamlari 4 × N bo’lgan ikki o’lchamli a massiv berilgan. a[t][i]a[t][i] bu tt-transport yordamida ii-shahardan (i+1)(i + 1)-shaharga borish uchun chipta narxi. Agar a[t][i]a[t][i] = −1 bo’lsa u holda bu transport bilan ii va (i+1)(i + 1)-shaharlar orasida yurib bo’lmaydi. Bundan tashqari, har bir transport uchun oylik abonement mavjud. Agar siz qaysidir transportga abonement sotib olsangiz undan tekinga xohlaganingizcha foydalanishingiz mumkin. tt-transport abonementi c[t]c[t] dollar turadi. Vazifangiz 1-shahardan (N+1)(N + 1)-shaharga borish uchun eng kamida qancha pul sarflash kerakligini topish. E’tibor bering, Dadorlandtiria mamlakatida barcha yo’llar bir tomonlik. Ya’ni i-shahardan (i+1)(i + 1)-shaharga o’tish mumkin, biroq (i+1)(i + 1)-shahardan ii-shaharga o’tib bo’lmaydi.


Kiruvchi ma'lumotlar:

Birinchi qatorda sizga N,c[1],c[2],c[3],c[4]N , c[1], c[2], c[3], c[4] sonlari beriladi - yo’llar soni va abonement narxlari.
Keyingi 4ta qatorda NN tadan butun son, ikki o’lchamli aamassiv elementlari.

Chegaralar
      • 1  N 1051 ≤   N  ≤ 10^5
      •1  c[t]  109 1 ≤   c[t]   ≤ 10^9 , barcha 1t41 ≤ t ≤ 4 uchun
      • 1  a[t][i]  109−1 ≤   a[t][i]   ≤ 10^9 , barcha 1t41 ≤ t ≤ 4 va 1 i    N1 ≤  i   ≤   Nuchun
Subtasks
      1. (11 ball) a[i][j]1a[i][j] ≠ −1 
      2. (10 ball) Abonement sotib olmasdan ham optimal javob topish mumkin.
      3. (20 ball) Faqat 1 ta transportga abonement sotib olish orqali optimal javob topish mumkin.
      4. (21 ball) Ko’pi bilan 2ta transportga abonement sotib olish orqali optimal javob topish mumkin.
      5. (29 ball) Faqatgina 1 - va/yoki 2 - turdagi transportlar orqali optimal javobni topish mumkin.
      6. (9 ball) Qo’shimcha chegaralarsiz.


Chiquvchi ma'lumotlar:

Yagona qatorda 1-shahardan (N+1)(N + 1)-shaharga borish uchun minimal pul miqdori.


Misollar
# input.txt output.txt
1
5 11 5 10 99
-1 5 4 -1 -1
4 -1 -1 -1 9
-1 8 -1 6 -1
10 10 10 10 10
19
Izoh:

Masalan, NN = 5, cc = [11, 5, 10, 99] bo’lsin. 2- va 3- transportlarga c[2]+c[3]c[2] + c[3] = 5 + 10 = 15 dollarga
abonement sotib olamiz. Shunda: 
* 1-shahardan 2-shaharga bepul boramiz. (2-transport orqali). 
* 2 shahardan 3-shaharga bepul boramiz. (3-transport orqali). 
* 3-shahardan 4-shaharga 4 dollar evaziga boramiz. (1-transport orqali). 
* 4-shahardan 5-shaharga bepul boramiz. (3-transport orqali). 
* 5-shahardan 6 shaharga bepul boramiz. (2-transport orqali). Jami 15 + 0 + 0 + 4 + 0 + 0 = 19 dollar ishlatdik. Ko’rsatish mumkinki 19 minimal javob.