There are NN items and a backpack with a capacity of VV. Each item can only be used once.
Item II has a volume of VIVI and a value of WIWII.
Figure out which items to put into the backpack so that the total volume of the items does not exceed the backpack capacity and the total value is maximum. Output maximum value.
Input format
In the first line, two integers, N, VN, V, separated by a space, represent the number of items and the volume of the backpack, respectively.
Then there are NN lines, each with two integers vi,wivi, and wi, separated by Spaces, representing the volume and value of item ii, respectively.
The output format
An integer is printed to indicate the maximum value.
Data range
0 < N, V < N, 10000 V or less 1000 0 or less < vi, wi 10000 or less < vi, wi 1000 or less
Enter the sample
4, 5, 1, 2, 2, 4, 3, 4, 5Output sample:
8