Биыл ICPC Әлем чемпионаты керемет Астанада өтуде! Чемпионаттың қатысушылары мен қонақтарына ыңғайлы болу үшін ұйымдастырушылар $N$ маңызды орындар: қонақ үйлер, жарыс өтетін орын, көрікті жерлер мен мейрамханалар арасында жүретін арнайы автобус-шаттл бөлді.

Автобус әрқашан негізгі жарыс өтетін орыннан (орын $1$) бастайды, келесі маршрут бойынша қозғалады: $1\to 2\to 3\to \cdots \to N-1\to N$. Әр орынға келгенде, алдымен қажетті орынға келген жолаушылар түседі, содан кейін жаңа жолаушылар (егер бос орын болса) кіреді.

Жарыс күні аяқталғаннан кейін ұйымдастырушылар сауалнама жүргізіп, $A_{i,j}$ — орын $i$-ден орын $j$-ға ($i<j$) көшуге ниет білдірген адамдардың санын анықтады.

Автобус дәл $K$ адамды сыйдыратыны белгілі. Шаттлдың барлық қонақтарды орындар арасында тасымалдау үшін, минималды қанша сапар жасауы тиіс екенін анықтаңыз.

Енгізу

Бірінші жолда екі бүтін сан $N$ және $K$ ($1\le N\le 100,1\le K\le 100$) — орындар саны мен автобустың сыйымдылығы сәйкесінше.

Келесі $N$ жолдың әрқайсысында $N$ бүтін сан бар, мұнда $i$-ші жолдағы $j$-ші сан $A_{i,j}$ ($0\le A_{i,j}\le 100$) орын $i$-ден орын $j$-ға жеткізгісі келетін адамдардың санын білдіреді. Барлық $j\le i$ үшін $A_{i,j}=0$ екеніне кепілдік беріледі.

Шығару

Мәселенің жауабын шығарыңыз.

Мысалдар

Енгізу 1

3 20
0 30 18
0 0 42
0 0 0

Жауап 1

3

Енгізу 2

4 20
0 45 30 18
0 0 38 20
0 0 0 15
0 0 0 0

Жауап 2

6