Masala #WOIRYZ41T4
RPG
Komiljon hozirda RPG turidagi kompyuter o'yinini o'ynamoqda. Hozirda uning vazifasi joni \(H\) birlikka teng maxluqni zarb etishdir. Maxluqning joni 0 yoki undan kamroq bo'lsa, u zarb etiladi.
Buning uchun u o'zida bor \(n\) ta \(1,2,\dots n\) bilan raqamlangan qurollaridan foydalana oladi. Biroq har bir qurol ko'pi bilan 1 marta ishlatilishi mumkin, bundan tashqari qaysidir qurolni ishlatganidan so'ng, Komiljon biroz vaqt ichida umuman hech qaysi qurollardan foydalana olmaydi.
Aytaylik Komiljon \(i\)-qurolini o'yin boshlanganidan \(x\) soniya o'tgach ishlatsin. Komiljonning ushbu qurolini ishga tushirganidan so'ng \(t_i\) soniya dam olishi kerak. Bu degani Komiljon \((x + t_i)\)-soniyagacha hech qaysi qurollardan foydalana olmaydi. Bundan tashqari qurol o'zining aktiv turish vaqti \(len_i\) ega. Yanada aniqroq aytsak, qurol ishga tushilrilganidan \((1 \leq j < len_i)\) soniya o'tkach, ya'ni o'yinning \((x + j)\)-soniyasida, maxluqning joni \(d_{i, j}\) miqdorga kamayadi. E'tibor bering, \(len_i\) soni \(t_i\) dan kattaroq bo'lishi mumkin. Ya'ni qurol ishga tushirilganch juda uzoq vaqt ishlab turilishi mumkin va uning effekti(aktiv turishi) boshqa qurollarniki bilan ustma ust bir vaqtda ishlatilishi mumkin.
O'yin 0-soniyada boshlanadi. Qurollarni to'g'ri ketma ketlikda ishlatgan holda, maxluqni eng minimal nechanchi soniya ichida zabt etib bo'lishini toping. Agar barcha qurollarini ishlatib bo'lgandan so'ng ham maxluq zabt etilmasa, ekranga \(-1\) chiqaring.
Kirish oqimining birinchi qatorida bitta butun son - \(T\) testlar soni kiritiladi.
Har bir test uchun alohida qatordan boshlab:
Birinchi qatorda ikkita butun son \(n(1 \leq n \leq 18)\) va \(H(1 \leq H \leq 10^{18})\) kiritiladi. Keyingi qatordan boshlab qurollarning xarakteristikasi beriladi.
Har bir qurol uchun 2 ta qatorda quyidagilar kiritiladi.
Birinchi qatorda ikkita butun son \(t_i\) va \(len_i(1 \leq t_i, len_i \leq 100 000)\). Ikkinchi qatorda \(len_i\) ta butun son, \(d_{i,0},d_{i,1}, \dots ,d_{i,len_i-1} (1 \leq d_{i,j} \leq 10^9)\) sonlari kiritiladi.
\(n > 10\) lik testlar soni 5 tadan oshmasligi hamda barcha testlardagi \(len_i\) lar yig'indisi \(3000000\) dan oshmasligi kafolatlanadi.
Har bir test uchun alohida qatoda, maxluqni zabt etiladigan minimal vaqtni chiqaring. Agar maxluqni zabt etishning iloji bo'lmasa, -1 chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 1 100 5 3 50 60 70 2 100 2 3 40 40 100 100 2 20 5 1 1000 1 1 999 |
1 2 -1 |
1-testda Komiljonning bitta quroli mavjud. Maxluqning joni esa 100.
0-soniyada Komiljon qurolini ishlatadi.
0-soniyada qurol \(d_{1,0} = 50\) miqdorga maxluqning jonini kamaytiradi
1-soniyada qurol \(d_{1,1} = 60\) miqdorga maxluqning jonini kamaytiradi. Shu bilan maxluq zarb etiladi. Shuning uchun ham javob 1.
Agar maxluqning joni ko'proq bo'lganida!
2-soniyada qurol \(d_{1,2} = 70\) miqdorga maxluqning jonini kamaytirardi.
Agar Komiljonning boshqa qurollari bo'lganida!
Komiljonning 5-soniyagacha dam olishi kerak bo'lardi va 5-soniyadan boshlab boshqa qurolini ishlata olardi.
Telegram kanalimizga obuna bo'ling