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

Автобус әрқашан негізгі жарыс өтетін орыннан (орын \(1\)) бастайды, келесі маршрут бойынша қозғалады: \(1 \rightarrow 2 \rightarrow 3 \rightarrow \cdots \rightarrow N - 1 \rightarrow 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