Ionel este un tip nerăbdător şi urăşte să aştepte. Din păcate, în fiecare zi trebuie să aştepte în staţia de tramvai, pentru că programul tramvaielor este afişat într-un mod foarte ciudat.
În loc să fie afişaţi timpii de sosire/plecare, pentru fiecare tramvai este afişată lista duratelor rutelor efectuate de tramvaiul respectiv.
Mai exact, prin staţia lui Ionel trec n tramvaie, pe care le vom numerota de la 1 la n. Fiecare tramvai i circulă pe m_i rute (în ordinea ruta 1, ruta 2, ..., ruta m_i, apoi după terminarea rutei m_i, tramvaiul reia de la ruta 1). Pentru fiecare rută este afişată durata necesară parcurgerii rutei respective (exprimată în minute).
Tramvaiele încep să circule de la momentul 0 (care corespunde zilei de 1 ianuarie, ora 00:00) şi circulă în acest mod o anumită perioadă stabilită de Primărie.

Cerinţă

Scrieţi un program care, cunoscând programul tramvaielor şi momentul în care Ionel a venit în staţie, să determine câte minute aşteaptă Ionel până soseşte în staţie primul tramvai.

Date de intrare

Fişierul de intrare tramvai.in conţine pe prima linie un număr natural n reprezentând numărul de tramvaie care circulă prin staţia lui Ionel.
Pe următoarele n linii sunt descrise rutele celor n tramvaie, câte un tramvai pe o linie. Pe linia i+1 este scris un număr natural m_i (numărul de rute parcurse de tramvaiul i), apoi o succesiune de m_i valori naturale reprezentând în ordine timpii necesari parcurgerii celor m_i rute. Pe ultima linie este scris timpul (exprimat în minute) la care soseşte Ionel în staţie. Numerele de pe aceeaşi linie sunt separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire tramvai.out va conţine o singură linie pe care va fi scris un singur număr natural, reprezentând câte minute trebuie să aştepte Ionel până soseşte în staţie primul tramvai.

Restricţii

• 1 <= n <= 20
• 1 <= m <= 10
• 1 <= timpul necesar pentru parcurgerea unei rute <= 1000
• 0 <= timpul la care soseşte Ionel în staţie <= 50000
• Dacă timpul la care Ionel soseşte în staţie coincide cu timpul la care ajunge în staţie un tramvai, atunci Ionel prinde tramvaiul, deci timpul de aşteptare va fi 0.

Exemple

tramvai.in	tramvai.out
3 3 400 500 600 3 100 200 300 3 700 900 800 1000	200

tramvai.in	tramvai.out
3 9 100 200 300 4 3 2 4 2 22 1 800 2 10 1000 3279	6

prof. Marinel Serban

Liceul de Informatica "Grigore Moisil" Iasi

marinel_serban@yahoo.com