시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 2 | 2 | 2 | 100.000% |
After the NASA sent their Mars Exploration Rovers Spirit and Opportunity to Mars, the ASAN decided to send their Venus Exploitation Rover Greedy to Venus in order to find out which valuable raw resources can be obtained from Venus. Its mission is to collect some stones from Venus’ surface.
Greedy will be transferred to Venus using a rocket that will drop it on the surface together with a large container, then fly seven times around Venus and finally pick up both Greedy and the container from the surface using its on-board grabbers.
After its landing, Greedy will use its IntelliSensor technology to scan for all interesting stones within half a mile. This will yield a list of stones with accurate estimations of their mass, their value for the Administratika and the time required to pick them up and put them in the container. The container is large enough to contain even all the stones, but the rocket can only lift a limited amount of mass from the surface. Also, the amount of time is limited due to the fact that the rocket will come back after seven rounds around Venus.
It is your task to write the program that will determine which of these stones to pick up and put in the container, if the total value is to be maximized.
The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:
For every test case in the input file, the output should contain a single number, on a single line: the maximum total value collectable in the corresponding test case.
2 1 20 10 2 2 100 5 20 10 6 6 10 10 5 12 5 10 18 12 5 10 3 3 7
100 19