Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_17_08 - Gra z potworami

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.

Dodane przez:Maciej Boniecki
Data dodania:2023-04-18
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM32-GCC COBOL D-CLANG D-DMD ELIXIR FANTOM GOSU GRV JS-MONKEY NIM OBJC OBJC-CLANG PICO RUST SCM qobi CHICKEN VB.NET

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.