플로우 숍

한 공장에서 곡물을 수확할 때 쓰는 예취기를 주문 제작한다. 모든 예취기는 같은 순서의 공정을 거친다. 절단 바를 달고, 곡물 벨트를 끼우고, 릴을 장착하는 식이다. 부품은 주문자의 요구에 맞춰 달라지므로 같은 공정이라도 예취기마다 걸리는 시간이 다르다.

예취기 $N$대를 주문받았고 제조 공정은 $M$단계다. 모든 예취기는 1번 공정부터 $M$번 공정까지 같은 순서로 지나간다.

$i$번 예취기의 $j$번 공정에는 시간 $P_{i,j}$가 걸린다. 한 공정의 작업자는 한 번에 예취기 한 대만 다루고, 한번 시작한 작업은 끝날 때까지 멈추지 않는다. 시각 0에 주문 $N$건이 모두 1번 공정 앞에 놓인다. $j$번 공정의 작업자가 쉬고 있고 그 공정 앞에 기다리는 예취기가 있으면, 작업자는 그중 번호가 가장 작은 예취기를 집는다. 예취기에는 1번부터 $N$번까지 번호가 붙어 있다. $j$번 공정은 같은 예취기의 $j-1$번 공정이 끝난 뒤에야 시작할 수 있다.

예취기마다 작업이 모두 끝나는 시각을 구하라.

첫째 줄에 예취기의 수 $N$과 공정의 수 $M$이 주어진다 ($1 \le N, M \le 1000$). 다음 $N$개 줄에는 각각 정수 $M$개가 주어진다. $i$번째 줄의 $j$번째 정수가 $P_{i,j}$다 ($1 \le P_{i,j} \le 10^6$).

한 줄에 정수 $N$개 $T_1\ T_2\ \dots\ T_N$을 공백 하나로 구분해 출력한다. $T_i$는 $i$번 예취기의 $M$번 공정이 끝나는 시각이다.