DMOPC '22 Contest 3 P4 - Sketchy Cereal

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 1.5s
Memory limit: 256M

Problem type

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 N boxes of cereal, the i-th having a price tag of c_i dollars and t_i tastiness. You have a budget of C 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 K pairs of cereal boxes, one pair after another, without getting caught. Given these conditions, what is the maximum total tastiness you can achieve?


1 \le N \le 10^3

1 \le C, c_i \le 2 \times 10^4

1 \le t_i \le 10^9

0 \le K \le N

Subtask 1 [40%]

1 \le N \le 200

0 \le K \le 5

Subtask 2 [30%]

1 \le N \le 200

0 \le K \le 50

Subtask 3 [30%]

No additional constraints.

Input Specification

The first line contains 3 integers N, C, and K.

The next N lines each contain 2 integers c_i and t_i.

Output Specification

Output the maximum total tastiness after swapping up to K pairs of price tags.

Sample Input

3 5 1
2 4
3 3
8 9

Sample Output


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 13.


There are no comments at the moment.