직사각형 칠하기

Srečko는 $m$개의 행($0$부터 $m-1$까지 번호가 붙음)과 $n$개의 열($0$부터 $n-1$까지 번호가 붙음)로 이루어진 직사각형 격자를 칠하려고 한다. 처음에는 격자의 모든 칸이 흰색이다. Srečko는 매 단계마다 대각선 하나를 골라 그 위의 모든 칸을 자신이 좋아하는 색으로 칠한다. 대각선마다 길이와 관계없이 칠하는 비용이 다르다. 각 대각선을 칠하는 비용이 주어질 때, 격자의 모든 칸을 칠하는 데 드는 최소 총비용을 구하여라. 칸은 두 번 이상 칠할 수 있다.

$m$개의 행과 $n$개의 열을 가진 직사각형 격자에는 $2m + 2n - 2$개의 대각선이 있다. 예를 들어 $m = 4$, $n = 3$이면 대각선은 12개이다:

입력은 세 줄로 이루어진다.

첫 줄에는 $m$과 $n$이 주어진다.

둘째 줄에는 ↘ 방향 대각선을 칠하는 비용을 나타내는 $m + n - 1$개의 수가 주어진다. $i$번째 수($i \in \{1, \dots, m+n-1\}$)는 행 번호와 열 번호의 차가 $i - n$인 대각선에 대응한다. 첫 번째 수는 칸 $(0, n-1)$만으로 이루어진 대각선에 대응하고, 두 번째 수는 칸 $(0, n-2)$와 $(1, n-1)$을 포함하는 대각선에 대응한다. 나머지도 같은 방식이다. 대각선의 순서는 위 그림의 첫 번째 행과 같다.

셋째 줄에는 ↗ 방향 대각선을 칠하는 비용을 나타내는 $m + n - 1$개의 수가 주어진다. $i$번째 수($i \in \{1, \dots, m+n-1\}$)는 행 번호와 열 번호의 합이 $i - 1$인 대각선에 대응한다. 첫 번째 수는 칸 $(0, 0)$만으로 이루어진 대각선에 대응하고, 두 번째 수는 칸 $(1, 0)$과 $(0, 1)$을 포함하는 대각선에 대응한다. 나머지도 같은 방식이다. 대각선의 순서는 위 그림의 두 번째 행과 같다.

격자를 칠하는 최소 비용을 출력한다.

$1 \le m \le 2 \cdot 10^5$

$1 \le n \le 2 \cdot 10^5$

비용은 $[1, 10^9]$ 구간의 정수이다.