LCC '24 Contest 1 J2 - Shopping Spree

View as PDF

Submit solution


Points: 3 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Bob is going shopping now! From the previous question, he figured out he has W cents to spend. At the store, he spots N items that catch his interest, each of which having its own value. Since he doesn't make the best financial decisions, if he is able to buy the current item with the amount of money he has left, he will always buy it. Please find the total value of the items he will purchase at the store! Note that he cannot skip items if he has the money to purchase it, and if he cannot purchase it, he will move onto the next item. Note that this means that he will always try to purchase every item in order.

Input Specification

The first line of input will contain two space-separated integers N, W, representing the number of items that caught his interest and the number of cents he has to spend, respectively.

The next N lines will contain values c_i and v_i, indicating the cost and value of the i^{th} item, respectively.

Output Specification

Output one integer, representing the value of the items he will purchase.

Subtasks

Subtask 1 [10%]

N = 1

W = 10

1 \le c_1, v_1 \le 20

Subtask 2 [90%]

1 \le N \le 2 \times 10^5

1 \le W, c_i \le 10^6

1 \le v_i \le 10^3

Sample Input 1

1 10
8 15

Sample Output 1

15

Sample Explanation 1

Bob has 10 cents, so he is able to purchase the one item with cost 8 cents, which gives a value of 15.

Sample Input 2

5 50
5 10 
45 1 
5 10
5 10
5 10

Sample Output 2

11

Sample Explanation 2

Bob can buy the first item, leaving him with 45 cents and a total value of 10. He spots the second item, and he has enough money to purchase it, so he instantly buys it (even though it gives less value than skipping this item and buying the last three), which gives him a total value of 11.


Comments

There are no comments at the moment.