FRAKTAL - konkurs programistyczny

Maciek gra w grę składającą się z n poziomów, ponumerowanych od 1 do n. Na każdym z nich znajduje się n potworów. Każdy potwór ma przypisaną pewną moc. Żeby przejść poziom numer x, nasz bohater musi pokonać dokładnie x z n potworów znajdujących się na tym poziomie. Jeżeli Maciek nie może przejść poziomu x to kończy grę. Nasz bohater pokona potwora tylko w przypadku, gdy moc jaką posiada jest większa od mocy potwora. Po przejściu każdego poziomu moc naszego bohatera zwiększa się o sumę mocy potworów pokonanych na danym poziomie.

Odpowiedz na pytanie, ile poziomów gry uda się przejść Maćkowi zakładając, że gra optymalnie?

Wejście

W pierwszej linii wejścia znajdują się dwie liczby całkowite n ∈ [4, 100] i m ∈ [1, 10] oznaczające odpowiednio liczbę poziomów oraz moc Maćka przed rozpoczęciem gry. W kolejnych n liniach znajdują się opisy poziomów, w kolejności od 1 do n.

Opis każdego poziomu składa się z n liczb całkowitych z przedziału [1, 200000], są to moce potworów znajdujących się na danym poziomie.

Wyjście

Na wyjściu należy wypisać odpowiedź na pytanie, ile poziomów gry uda się przejść Maćkowi zakładając, że gra optymalnie?

Przykład

Wejście:

4 2
7 1 51288 4
7 1 8 2
3 2 39988 3
50 11 13 90

Wejście:

3

Wyjaśnienie do przykładu:

• Na 1 poziomie Maciek pokonuje potwora numer 2 o mocy 1. Po przejściu poziomu moc Maćka wynosi 2 + 1 = 3.
• Na 2 poziomie Maciek pokonuje potwory numer 2 i 4 o mocach 1 i 2. Po przejściu poziomu moc Maćka wynosi 3 + 1 + 2 = 6.
• Na 3 poziomie Maciek pokonuje potwory numer 1, 2 i 4 o mocach 3, 2 i 3. Po przejściu poziomu moc Maćka wynosi 6 + 3 + 2 + 3 = 14.
• Na 4 poziomie Maciek jest w stanie pokonać tylko potwory numer 2 i 3, a zatem nie jest w stanie przejść tego poziomu.