Plovdiv의 유명한 초콜릿 판매업자 Bonny는 건포도 초콜릿을 자르려 한다.
초콜릿은 동일한 직사각형 크기로 나눠져야 한다. 조각은 초콜릿의 모서리에 따라 가지런히 놓여있으며 N열 M행으로 총 N*M조각으로 되어있다. 각 초콜릿 조각에는 하나이상의 건포도를 포함하고 있으며 초콜릿 조각 사이나 초콜릿 조각을 가로질러 있는 건포도는 없다.
처음 초콜릿은 한덩어리 이다. Bonny는 이 초콜릿 조각을 더 작은 조각으로 자르고 잘라 N*M조각이 되도록 해야한다. Bonny가 매우 바쁜 관계로 그녀를 도울 조수 Sly Peter에게 자르는 일을 시킨다. Peter는 오르지 일직선으로만 초콜릿을 자르며 한번 자를때 마다 일정한 양의 보상을 받기 원한다. Bonny는 현재 수중에는 돈이없지만, 많은 양의 건포도가 남아있다. 따라서 Peter에게 남은 건포도를 보상으로 주려 한다. Sly Peter는 그러기로 동의했지만 다음과 같은 조건을 내세웠다.
조건: 초콜릿 한 조각을 두 조각으로 나눌때 마다 그 초콜릿 속에 든 건포도의 개수만큼 받아야 한다.
Bonny는 Peter에게 가능한 적은 양의 건포도를 주려한다. 그녀는 N*M 조각들에 얼마나 많은 건포도가 들어있는지 안다. 그녀는 Peter에게 줄 남은 초콜릿 조각의 순서를 정해 줄수 있으며, Peter에게 세로로 자를지 가로로 자를지 정해 줄수 있다. Bonny가 초콜릿을 N*M 조각으로 나누기 위해 어떻게 해야 Peter에게 가능한 적은 양의 건포도를 줄수있는지 도와줘야한다.
입력 2 3 2 7 5 1 9 5 출력 77
The first cut that Bonny asks Peter to make separates the third column from the rest of the chocolate. Bonny needs to pay Peter 29 raisins for this.
Then Bonny gives Peter the smaller of the two blocks: the one that has two pieces with 5 raisins each, and asks Peter to cut the block in two in exchange for 10 raisins.
After this, Bonny gives Peter the largest remaining block: the one having pieces with 2, 7, 1 and 9 raisins respectively. Bonny asks Peter to cut it horizontally, separating the first and the second row and pays him 19 raisins.
Following this, Bonny gives Peter the top-left block, paying 9 raisins. Finally, Bonny asks Peter to split the bottom-left block, paying 10 raisins.
The total cost to Bonny is 29 + 10 + 19 + 9 + 10 = 77 raisins. No other cutting arrangement can get the chocolate cut into its 6 pieces at a smaller cost.
출처: International Olympiad In Informatics 2009 번역: makesource