A ground station broadcasts a shared calibration beam to a small fleet of n satellites. The beam starts at output rate 1 unit per minute, and every satellite draws from the same shared energy pool, which begins empty and grows by the current beam rate every minute. Satellite i needs its pool exposure to reach at least c_i units before it can be calibrated. At any whole-minute mark when the pool holds at least c_i units, the station may choose to calibrate satellite i: doing so immediately drains the pool back to zero and permanently increases the beam's rate by a fixed amount K, effective from that same minute onward, in exchange for one fewer satellite competing for bandwidth. Each satellite is calibrated exactly once, and the station chooses the order of calibration.

Given the beam's rate increment K and each satellite's requirement, determine the minimum total number of minutes needed to calibrate every satellite, choosing the calibration order that minimizes this total.

Input format

Line 1: two space-separated integers n and K — the number of satellites and the fixed amount by which the beam's rate increases after each calibration. Line 2: n space-separated integers c_1 ... c_n — the calibration requirement of each satellite.

Output format

Print a single integer: the minimum total number of minutes needed to calibrate all n satellites under an optimal calibration order.

Constraints

• 1 <= n <= 8
• 1 <= K <= 10
• 1 <= c_i <= 10^6

2 1
3 4

5

3 2
1 1 1

3