407931: GYM102944 H Holland

You are a manager of a beautiful but tiny take-out-only restaurant in Holland, a scenic city in western Michigan. All of your customers are regulars and you know that there will be $$$N$$$ customers planning to order food from your restaurant today. You even know the arrival time of each customer, the food that customer will order, and the tip that customer will leave. (You have studied data science so you can predict these things perfectly!) The restaurant service works as follows. When a customer arrives at the front door, they will enter a waiting queue. Your restaurant always serves the customer at the front of the queue. After this customer gets their food they will leave the restaurant immediately and then you are able to serve the next customer. However, due to social distancing limitations these days, your restaurant can hold at most $$$K$$$ customers at one time so you set this as the maximum queue size. Whenever a customer arrives at your restaurant and finds a full queue, that customer flies into a rage and leaves immediately. (If the queue is completely full with $$$K$$$ customers and the customer at the front of the queue is served at exactly the same time that a $$$(K+1)$$$st customer arrives to join the queue, there is no problem: the served customer at the front will exit and the arriving customer will join the queue simultaneously – rage avoided.)

As an awesome manager, you would like to avoid the potential frustration from these customers. To do so, you would select a subset of customers and tell them not to order food today, so that all the remaining customers can be served. As a clever manager, you would like to maximize the total amount of tips you get from the remaining customers.

The first line contains three integers $$$N$$$, $$$K$$$, and $$$S$$$ ($$$1\le K\le N\le 1000, 1\le S\le 10^6$$$), indicating the number of customers planning to order food from you today, the size of a queue, and the amount of time it takes to serve one customer. In each of the following $$$N$$$ lines, there are two values $$$a_i$$$ and $$$t_i$$$ ($$$1\le a_i \le 10^9, 1\le t_i\le 10^6$$$), indicating the arrival time and the amount of tips you receive if they are served.

Output the maximum possible amount of tips you can get.

3 2 10
1 100
6 200
8 300

500

3 2 10
1 100
6 200
12 100

400

3 1 10
1 100
6 200
17 100

300

10 3 10
1 120
4 105
8 134
11 104
13 114
26 111
17 113
16 126
19 111
25 129

623

In the 4-th example, we should choose the customers that arrive at time $$$1, 8, 13, 16, $$$ and $$$25$$$. In this way, the total tips we can get is $$$120+134+114+126+129=623$$$.