레이팅 미적용August 8 – 15, Plovdiv, Bulgaria
Contest Day 1 - Raisins
English 1.1
건포도 (RAISINS)
플로브디프의 유명한 쇼콜라티에 장인 Bonny는 건포도가 박힌 초콜릿 판을 잘라야 한다. 초콜릿은 동일한 정사각형 조각들로 이루어진 직사각형 판이다. 조각들은 초콜릿의 가장자리와 평행하게 정렬되어 있으며, N개의 행과 M개의 열, 총 N*M개의 조각으로 배열되어 있다. 각 조각 위에는 건포도가 하나 이상 있으며, 조각 사이나 조각에 걸쳐 있는 건포도는 없다.
처음에 초콜릿은 하나의 통짜 판이다. Bonny는 초콜릿이 마침내 N*M개의 개별 조각으로 나뉠 때까지 점점 더 작은 판으로 잘라야 한다. Bonny는 매우 바쁘기 때문에 조수인 교활한 Peter의 도움이 필요하다. Peter는 직선으로 끝에서 끝까지 자르는 것만 하며, 자를 때마다 대가를 받고 싶어 한다. Bonny는 수중에 돈이 없지만 건포도가 많이 남아 있어서 Peter에게 건포도로 대가를 지불하겠다고 제안한다. 교활한 Peter는 다음 조건 하에 이에 동의한다: 그가 주어진 초콜릿 판을 두 개의 더 작은 판으로 자를 때마다, 그가 받은 판 위에 있는 건포도 수만큼 건포도를 받아야 한다.
Bonny는 Peter에게 가능한 한 적게 지불하고 싶다. 그녀는 N*M개의 각 조각 위에 건포도가 몇 개 있는지 알고 있다. 그녀는 남은 판들을 Peter에게 주는 순서를 정할 수 있고, Peter에게 어떤 방향(가로 또는 세로)으로 정확히 어디를 자를지 지시할 수도 있다. Bonny가 교활한 Peter에게 지불하는 건포도가 최소가 되도록 초콜릿을 개별 조각으로 자르는 방법을 결정하도록 도와주시오.
TASK
각 개별 조각 위의 건포도 수가 주어졌을 때, Bonny가 교활한 Peter에게 지불해야 하는 건포도의 최소 개수를 구하는 프로그램을 작성하시오.
EXAMPLE
Sample Input
Sample Output
2 3
2 7 5
1 9 5
77
비용 77을 달성하는 (많은 방법 중) 한 가지 방법은 다음과 같다:
Bonny가 Peter에게 부탁하는 첫 번째 자르기는 세 번째 열을 나머지 초콜릿에서 분리하는 것이다. 이를 위해 Bonny는 Peter에게 건포도 29개를 지불해야 한다.
그다음 Bonny는 두 판 중 더 작은 것, 즉 건포도가 5개씩 있는 두 조각으로 이루어진 판을 Peter에게 주고, 건포도 10개를 대가로 그 판을 둘로 자르게 한다.
그 후 Bonny는 남은 것 중 가장 큰 판, 즉 건포도가 각각 2, 7, 1, 9개인 조각들로 이루어진 판을 Peter에게 준다. Bonny는 첫 번째 행과 두 번째 행을 분리하도록 가로로 자르게 하고 건포도 19개를 지불한다.
이어서 Bonny는 왼쪽 위 판을 Peter에게 주고 건포도 9개를 지불한다. 마지막으로 Bonny는 왼쪽 아래 판을 자르게 하고 건포도 10개를 지불한다.
Bonny의 총비용은 29 + 10 + 19 + 9 + 10 = 77개의 건포도이다. 다른 어떤 자르기 방식으로도 이보다 적은 비용으로 초콜릿을 6개의 조각으로 자를 수 없다.
\(1 \le N, M \le 50\)
초콜릿의 각 변에 있는 조각의 수
\(1 \le Rk,p \le 1000\)
k번째 행, p번째 열의 조각 위에 있는 건포도의 수
프로그램은 표준 입력에서 다음 데이터를 읽어야 한다:
• 첫 줄에는 정수 N과 M이 공백 하나로 구분되어 주어진다.
• 다음 N개의 줄에는 초콜릿의 각 조각 위에 건포도가 몇 개 있는지가 주어진다. 이 N개의 줄 중 k번째 줄은 초콜릿의 k번째 행을 나타낸다. 각 줄에는 공백 하나로 구분된 M개의 정수가 있다. 이 정수들은 해당 행의 조각들을 왼쪽에서 오른쪽 순서로 나타낸다. (이 N개의 줄 중) k번째 줄의 p번째 정수는 k번째 행, p번째 열의 조각 위에 건포도가 몇 개 있는지를 나타낸다.
프로그램은 표준 출력에 정수 하나가 있는 한 줄을 출력해야 한다: Bonny가 교활한 Peter에게 지불해야 하는 건포도의 최소 개수.
August 8 – 15, Plovdiv, Bulgaria
Contest Day 1 - Raisins
English 1.1
GRADING
총 25점에 해당하는 여러 테스트에서 N과 M은 7을 넘지 않는다.