You are given an array loads of length N, where loads[i] denotes the number of pieces in the i-th load. You are also given an even integer K representing the number of warehouses.

Each warehouse can receive pieces from only one load, but a load may be split among multiple warehouses.

After distributing all pieces into exactly K warehouses, let warehouse[i] denote the total pieces assigned to the i-th warehouse.

Sort the warehouse loads in non-decreasing order and discard the largest K/2 warehouse loads.

Your task is to maximize the sum of the remaining K/2 smallest warehouse loads.

Return the maximum possible value.

---

Input Format

• The first line contains two integers N and K.
• The second line contains N integers representing loads[i].

---

Output Format

Print a single integer — the maximum possible sum of the smallest K/2 warehouse loads after an optimal distribution.

---

Constraints

• 1 ≤ N ≤ 2 × 10^5
• 2 ≤ K ≤ 2 × 10^5
• K is even.
• 1 ≤ loads[i] ≤ 10^9
• Every warehouse must receive a non-negative number of pieces.
• Every warehouse receives pieces from exactly one load.
• A load may be split across multiple warehouses.

---

Example 1

Input

3 4
8 5 3

Output

5

Explanation

One optimal distribution is:

• Load 8 → 3, 5
• Load 5 → 5
• Load 3 → 3

Warehouse loads become:

3 3 5 5

After sorting:

3 3 5 5

Discard the largest 2 warehouses:

5 5

Remaining sum:

3 + 3 = 6

Thus, the maximum possible answer is 6.

---

Example 2

Input

2 2
10 6

Output

6

Explanation

Assign one load to each warehouse:

10 6

After sorting:

6 10

Discard the largest warehouse (10).

Remaining sum is:

6

Hence, the answer is 6.