Weapons X75800


Statement
 

pdf   zip

After each stage of the video game, the player has the option of buying weapons using money gathered from killing enemies. The ship can carry a single copy of each weapon, each of which has a price and a damage rate. The total damage rate of the ship equals the sum of the damage rate of its weapons. However, not all weapons are available for purchase at any given time. Help the player optimize the purchase of weapons to maximize the damage rate.

Input

The input begins with an integer 1≤N≤10001\leq N\leq 1000 representing the number of weapons. On the next NN lines appear the price 1≤P≤10001\leq P\leq 1000 and damage rate 1≤D≤10001\leq D\leq 1000 of each weapon.

Several test cases follow. Each test case consists of the player’s money 1≤M≤10001\leq M\leq 1000, the number of available weapons 1≤K≤N1\leq K\leq N, and the KK indices of the available weapons.

Output

For each test case, a number on a single line representing the maximum damage rate of weapons that the player can buy with their money.

Public test cases

  • Input

    1
1 5

1 1 1

    Output

    5

  • Input

    2
1 5
2 10

1 2 1 2
2 2 1 2
3 2 1 2

    Output

    5
10
15

  • Input

    5
3 7
7 13
11 23
13 29
17 37

10 2 1 4
20 3 1 2 4
30 3 2 3 5
40 5 1 2 3 4 5

    Output

    7
42
60
86
    • Information
    Author
    Anders Jonsson
    Language
    English
    Official solutions
    Unknown.
    User solutions
    C++