There is a large, circular, one-way road, driven on by a number of evenly spaced buses, with an equal number of evenly spaced bus stations placed next to it. Each bus and station belongs to one of ~N~ colours. There are ~a_i~ buses and ~a_i~ stations of the ~i^{\text{th}}~ colour (~1 \le i \le N~). Over a period of time, buses will drive clockwise, remaining spaced equally, each passing exactly ~X~ stations, and then stop moving. You are allowed to permute all of the buses and stations however you want before the buses start driving. When a bus passes a station of the same colour, the bus will visit it. You must find the maximum number of visits that can occur.

Note that a bus can visit the same station multiple times.

Constraints

~1 \le N \le 2 \times 10^5~

~1 \le a_i \le 10^6~

~0 \le X \le 2 \times 10^{11}~

Subtask 1 [10%]

~\sum_{i=1}^{i=N} a_i \le 5 \times 10^3~

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line contains two integers, ~N~ and ~X~.

The second line contains ~N~ integers, ~a_i~.

Output Specification

Output a single line containing an integer, the maximum number of times buses will visit a station.

Sample Input

2 3
2 2

Sample Output

8

Explanation for Sample

We can place buses and stops like this (the first row is the stops, and the second row is the buses):

2 2 1 1
1 1 2 2

Since ~X=3~, we will need to consider ~3~ positions:

At time ~0~, there are ~2~ visits:

2 2 1 1
2 1 1 2

At time ~1~, there are ~4~ visits:

2 2 1 1
2 2 1 1

At time ~2~, there are ~2~ visits:

2 2 1 1
1 2 2 1