You are given an N \times M grid. On each cell (i, j), there is a stack of H_{i, j} non-negative integer boxes.
You are given two arrays:
F of size M representing the Front View. Formally, for each column j (1 \le j \le M), F_j = \max_{1 \le i \le N} H_{i, j}.
L of size N representing the Left View. Formally, for each row i (1 \le i \le N), L_i = \max_{1 \le j \le M} H_{i, j}.
Find the maximum total number of boxes (\sum H_{i, j}) that can be on the board such that the Front and Left views remain exactly as specified.
Input
The first line contains two integers N and M (1 \le N, M \le 100).
The second line contains M integers F_1, F_2, \dots, F_M (1 \le F_j \le 10^9), where F_j is the maximum height in column j.
The third line contains N integers L_1, L_2, \dots, L_N (1 \le L_i \le 10^9), where L_i is the maximum height in row i.
It is guaranteed that at least one valid configuration of H_{i, j} exists.
Output
Print a single integer — the maximum total number of boxes possible.
Examples
| standard input | standard output |
|---|
| 2 2
3 4
4 3
| 13
|