100 Great Ukrainians
The premise of a popular television show is as follows: A number of nominations for notable individuals who lived in Ukraine during a specific period are presented. Then, invited guests in the studio and viewers discuss the various candidates. However, the most intriguing part occurs after the show ends. Phone numbers are broadcasted, allowing anyone to send an SMS from their phone (costing 1 hryvnia) to vote for their preferred candidate. Each SMS gives the chosen candidate 1 vote. After a certain period, the SMS votes are counted, and a set number of candidates with the highest votes are declared Great. If there is a tie among candidates that would exceed the specified number of Greats, none of those tied, nor those with lower votes, are considered Great.
A particular socio-political organization wants to ensure that some of its chosen candidates are included in the list of Greats. A day before the results are finalized, this organization learns the current vote counts for all candidates, which may not guarantee their desired outcome. Since repeated SMS votes from the same number are not counted, a member of this organization takes to the streets, asking passersby to send an SMS for the candidate he specifies. The organization reimburses the cost of sending the SMS, so the passerby immediately gets their hryvnia back.
Additionally, there is another organization whose aim is to thwart the first organization's plan to promote its candidates. A representative from this second organization also starts asking passersby to send messages for the candidates they support.
Given the amount of money the second organization has available, determine the minimum amount the first organization needs to spend to ensure its candidates become Great Ukrainians, even with the best counter-strategy from the second organization.
Assume the population is large enough that each representative can find the necessary number of passersby. Furthermore, in the remaining time before the results are finalized, no ordinary person will spend their own money on such matters.
Input
The first line contains 3 integers: N - the total number of candidates, M - the number of Greats, K - the number of candidates being promoted by the first organization. The second line contains the sum S, which is the budget of the second organization (1 ≤ K ≤ M ≤ N ≤ 10^5, 0 ≤ S ≤ 10^9). The third line contains the ratings A_i (i={1...N}) - the current vote counts for the candidates (0 ≤ A_i ≤ 10^9). The fourth line contains the indices B_j (j={1...K}), which specify the candidates that need to be made Great.
Output
Output the minimum amount the first organization needs to spend to achieve its goal.