题目描述

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.

输入格式

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 a single line with an integer indicating the maximum total profit Drew can achieve.

3 1 0
6 4 14

2

3 1 1
6 4 14

7

提示

Explanation of Sample 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 of Sample 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.