문제
석표는 긴 도로를 따라 석유가 나는 땅을 가지고 있다.
이 땅의 지하는 깊이 N칸, 길이 M칸의 격자로 나타낼 수 있다.
각 칸에는 0~9로 표시되는 양의 석유가 들어있거나, '.' 으로 표시되는 암반이 있다.
석표는 이 땅들 중 몇 칸을 골라 수직으로 쭉 파이프를 꽂아 석유를 시추할 것이다.
파이프를 꽂으면 그 줄의 모든 칸에 있는 석유와 그 칸들에 연결되어 있는 석유를 모두 시추할 수 있다.
석표는 이 사업에 얼마나 투자가 이루어질지 모르기 때문에 여러 안을 기획하고 있다.
석표는 1개의 파이프를 꽂는 안부터 M개의 파이프를 꽂는 안까지 모든 경우에 대해 시추할 수 있는 석유의 최대 양을 알고 싶다.
착한 여러분이 석표를 도와주도록 하자.
입력
첫 줄에 N, M이 차례로 주어진다.
다음줄부터 지하에 있는 석유의 정보가 주어진다.
1 <= N, M <= 2000
출력
M줄에 걸쳐 i번째 줄에는 i개의 파이프를 꽂았을 때 얻을 수 있는 최대의 석유 양을 출력한다.
예제 #1
5 5
...3.
....1
..0.3
489..
.....
21
25
28
28
28
예제 #2
3 5
999.1
.....
1.999
54
56
56
56
56
예제 #3
5 5
.27..
7.063
....7
78...
8...2
48
57
57
57
57
출처
songc
로그인해야 코드를 작성할 수 있어요.