석표는 긴 도로를 따라 석유가 나는 땅을 가지고 있다.

이 땅의 지하는 깊이 N칸, 길이 M칸의 격자로 나타낼 수 있다.

각 칸에는 0~9로 표시되는 양의 석유가 들어있거나, '.' 으로 표시되는 암반이 있다.

석표는 이 땅들 중 몇 칸을 골라 수직으로 쭉 파이프를 꽂아 석유를 시추할 것이다.

파이프를 꽂으면 그 줄의 모든 칸에 있는 석유와 그 칸들에 연결되어 있는 석유를 모두 시추할 수 있다.

석표는 이 사업에 얼마나 투자가 이루어질지 모르기 때문에 여러 안을 기획하고 있다.

석표는 1개의 파이프를 꽂는 안부터 M개의 파이프를 꽂는 안까지 모든 경우에 대해 시추할 수 있는 석유의 최대 양을 알고 싶다.

착한 여러분이 석표를 도와주도록 하자.

석유 시추 timer 2s memory 512MB

석유 시추 2s 512MB