#abc224h. [abc224_h]Security Camera 2
[abc224_h]Security Camera 2
Problem Statement
We have a bipartite graph with vertices to the left and vertices to the right.
Takahashi will install surveillance cameras in these vertices.
Installing cameras incurs the following cost.
- yen (the Japanese currency) for each camera installed in the -th vertex to the left;
- yen (the Japanese currency) for each camera installed in the -th vertex to the right.
It is allowed to install multiple cameras on the same vertex.
Find the minimum amount of money needed to install cameras to satisfy the following condition.
- For every pair of integers such that , there is a total of or more cameras installed in the -th vertex to the left and -th vertex to the right.
Constraints
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
Print the answer as an integer.
Sample Input 1
Sample Output 1
You can achieve the objective for yen as follows, which is the minimum amount required.
- Install cameras on the -st vertex in the left.
- Install cameras on the -nd vertex in the left.
- Install cameras on the -rd vertex in the left.
- Install camera on the -st vertex in the right.
- Install camera on the -rd vertex in the right.
Sample Input 2
Sample Output 2
No camera may be needed.