D. Dropshipping
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Drew P. Shipper received $$$N$$$ customer requests for products sold at a store called EvenBuy, where all product prices are even integers. To fulfill the $$$i$$$-th request, Drew must purchase a specific product that costs $$$A_i$$$ at EvenBuy, and Drew has already charged this price to the customer.

Drew is doing this for profit, based on a loyalty program that EvenBuy has: after Drew makes $$$X$$$ full-price purchases, he gets a discount of 50% in his next single purchase. This discounted purchase does not count toward the $$$X$$$ full-price purchases required to earn the next discount. Because Drew's customers paid him the full price upfront, he keeps the amount of the discount as his own profit whenever he purchases a discounted item.

Drew can decide the order of his purchases at EvenBuy to maximize his total profit. However, delivery times are directly related to the order of the purchases, and to avoid customer complaints, he cannot delay a purchase too much. In practice, Drew must fulfill the $$$i$$$-th request within his first $$$i + K$$$ purchases at EvenBuy.

Your task is to find the maximum total profit Drew can achieve. Each purchase fulfills exactly one request and each request must be fulfilled exactly once.

Input

The first line contains three integers $$$N$$$, $$$X$$$ ($$$1 \le N, X \le 2 \times 10^{5}$$$) and $$$K$$$ ($$$0 \le K \le 2 \times 10^{5}$$$), indicating respectively the number of customer requests, the number of full-price purchases required to get a 50% discount, and the delivery limit (the $$$i$$$-th request must be fulfilled within the first $$$i + K$$$ purchases).

The second line contains $$$N$$$ even integers $$${A_1}, {A_2}, \ldots, {A_N}$$$ ($$$2 \le A_i \le 10^{9}$$$), representing the prices of the requested products.

Output

Output a single line with an integer indicating the maximum total profit Drew can achieve.

Examples
Input
3 1 0
6 4 14
Output
2
Input
3 1 1
6 4 14
Output
7
Note

Explanation for example 1

Since $$$K = 0$$$, the $$$i$$$-th request must be fulfilled with the $$$i$$$-th purchase. As only the second purchase is discounted, Drew can only achieve a profit of $$$4 / 2 = 2$$$.

Explanation for example 2

Now the $$$i$$$-th request must be fulfilled within the first $$$i+1$$$ purchases. So the valid purchase orders are $$$[6, 4, 14]$$$, $$$[6, 14, 4]$$$, $$$[4, 6, 14]$$$ and $$$[14, 6, 4]$$$. The order $$$[6, 14, 4]$$$ is the best, as Drew can achieve a profit of $$$14 / 2 = 7$$$ on the second purchase.