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