PIIMA

Xotira 128 MB Vaqt 2000 ms

14

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.

Kiruvchi ma'lumotlar:

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.

Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatoda, maxluqni zabt etiladigan minimal vaqtni chiqaring. Agar maxluqni zabt etishning iloji bo'lmasa, -1 chiqaring.

Misollar

#	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

Izoh:

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.

Masala C

RPG