As a broke university student who finally has time to go shopping for the first time in months, you decide to go on a cereal haul as motivation to actually eat breakfast next semester. At the supermarket, you see boxes of cereal, the -th having a price tag of dollars and tastiness. You have a budget of dollars, and would like to maximize the total tastiness of the cereal you buy.
Money is tight though, and sometimes you have to resort to some morally questionable tricks up your sleeve to maximize the efficiency of your spending. While shopping for the cereal, you have time to sneakily swap the price tags of up to pairs of cereal boxes, one pair after another, without getting caught. Given these conditions, what is the maximum total tastiness you can achieve?
Subtask 1 [40%]
Subtask 2 [30%]
Subtask 3 [30%]
No additional constraints.
The first line contains integers , , and .
The next lines each contain integers and .
Output the maximum total tastiness after swapping up to pairs of price tags.
3 5 1 2 4 3 3 8 9
Explanation for Sample
We can swap the price tags of the second and third cereal boxes, then buy the first and the third boxes for a total tastiness of .