현재 테이블 위에 N행 M열 격자 모양 초콜릿이 있다. 우리는 이 초콜릿을 잘게 잘라서 1 × 1 크기 조각 N × M개를 만들려고 한다. 초콜릿을 자를 때에는 각 칸 사이의 가로줄 또는 세로줄 경계선을 한 번에 부러뜨려서 나눈다. 각 경계선별로 초콜릿을 예쁘게 자르기 위한 난이도가 다른데, i열과 i+1열 사이의 세로줄 경계선을 자르는 난이도는 x_i(1 ≤ i ≤ M-1)이고, i행과 i+1행 사이의 가로줄 경계선을 자르는 난이도는 y_i(1 ≤ i ≤ N-1)이다. 아래 그림은 초콜릿을 자르는 난이도를 설명하는 그림이다.

초콜릿을 자르는 총 난이도는 개별 단계에서 초콜릿을 자르는 난이도의 합과 같다. 초콜릿을 자르는 방법에 따라 같은 경계선을 따라 초콜릿을 여러 번 잘라야 할 수도 있는데, 위 그림의 초콜릿을 모든 가로줄 경계선으로 먼저 자르고 세로줄 경계선으로 자른다면, 총 난이도는 y₁+y₂+y₃+4⋅(x₁+x₂+x₃+x₄+x₅)이다.

초콜릿의 정보가 주어지면 초콜릿을 자르는 최소 난이도를 구하는 프로그램을 작성하여라.

#2041 upload 2 done 1 how_to_reg 1

초콜릿 자르기 timer 1s memory 32MB

#2041

초콜릿 자르기 1s 32MB