Problems
현재 테이블 위에 N행 M열 격자 모양 초콜릿이 있다. 우리는 이 초콜릿을 잘게 잘라서 1 × 1 크기 조각 N × M개를 만들려고 한다. 초콜릿을 자를 때에는 각 칸 사이의 가로줄 또는 세로줄 경계선을 한 번에 부러뜨려서 나눈다. 각 경계선별로 초콜릿을 예쁘게 자르기 위한 난이도가 다른데, i열과 i+1열 사이의 세로줄 경계선을 자르는 난이도는 xi(1 ≤ i ≤ M-1)이고, i행과 i+1행 사이의 가로줄 경계선을 자르는 난이도는 yi(1 ≤ i ≤ N-1)이다. 아래 그림은 초콜릿을 자르는 난이도를 설명하는 그림이다.
초콜릿을 자르는 총 난이도는 개별 단계에서 초콜릿을 자르는 난이도의 합과 같다. 초콜릿을 자르는 방법에 따라 같은 경계선을 따라 초콜릿을 여러 번 잘라야 할 수도 있는데, 위 그림의 초콜릿을 모든 가로줄 경계선으로 먼저 자르고 세로줄 경계선으로 자른다면, 총 난이도는 y1+y2+y3+4⋅(x1+x2+x3+x4+x5)이다.
초콜릿의 정보가 주어지면 초콜릿을 자르는 최소 난이도를 구하는 프로그램을 작성하여라.
Input
첫 번째 줄에는 초콜릿의 크기 M, N이 주어진다. (2 ≤ M, N ≤ 1,000)
두 번째 줄부터 M-1개의 줄에는 초콜릿을 세로로 자르는 난이도 x1, x2, …, xm-1 이 주어진다. (1 ≤ xi ≤ 1,000)
다음 N-1개의 줄에는 초콜릿을 가로로 자르는 난이도 y1, y2, …, yn-1 이 주어진다. (1 ≤ yi ≤ 1,000)
Output
첫 번째 줄에 초콜릿을 자르는 최소 난이도를 출력한다.
Example
6 4
2
1
3
1
4
4
1
2
42
Tag
Source
Polish Olympiad in Informatics 2002/2003 1차대회 2번
You must sign in to write code.