The Berland Army is preparing for a large military parade. It is already decided that the soldiers participating in it will be divided into \(k\) rows, and all rows will contain the same number of soldiers.
Of course, not every arrangement of soldiers into \(k\) rows is suitable. Heights of all soldiers in the same row should not differ by more than \(1\). The height of each soldier is an integer between \(1\) and \(n\).
For each possible height, you know the number of soldiers having this height. To conduct a parade, you have to choose the soldiers participating in it, and then arrange all of the chosen soldiers into \(k\) rows so that both of the following conditions are met:
- each row has the same number of soldiers,
- no row contains a pair of soldiers such that their heights differ by \(2\) or more.
Calculate the maximum number of soldiers who can participate in the parade.
Output
For each test case, print one integer — the maximum number of soldiers that can participate in the parade.
Note
Explanations for the example test cases:
- the heights of soldiers in the rows can be: \([3, 3, 3, 3]\), \([1, 2, 1, 1]\), \([1, 1, 1, 1]\), \([3, 3, 3, 3]\) (each list represents a row);
- all soldiers can march in the same row;
- \(33\) soldiers with height \(1\) in each of \(3\) rows;
- all soldiers can march in the same row;
- all soldiers with height \(2\) and \(3\) can march in the same row.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 4
7 1 13
1 1
100
1 3
100
2 1
1000000000000 1000000000000
4 1
10 2 11 1
|
16
100
99
2000000000000
13
|