Time Limit: Java: 2000 ms / Others: 2000 ms
Memory Limit: Java: 65536 KB / Others: 65536 KB
In Zhejiang University Programming Contest, a team is called "couple team" if it consists of only two students loving each other. In the contest, the team will get a lovely balloon with unique color for each problem they solved. Since the girl would prefer pink balloon rather than black balloon, each color is assigned a value to measure its attractiveness. Usually, the boy is good at programming while the girl is charming. The boy wishes to solve problems as many as possible. However, the girl cares more about the lovely balloons. Of course, the boy's primary goal is to make the girl happy rather than win a prize in the contest.
Suppose for each problem, the boy already knows how much time he needs to solve it. Please help him make a plan to solve these problems in strategic order so that he can maximize the total attractiveness value of balloons they get before the contest ends. Under this condition, he wants to solve problems as many as possible. If there are many ways to achieve this goal, he needs to minimize the total penalty time. The penalty time of a problem is equal to the submission time of the correct solution. We assume that the boy is so clever that he always submit the correct solution.
The first line of input is an integer N (N T (T n (n n integers and the i-th integer ti (ti n integers and the i-th integer vi (vi i-th problem. Time is measured in minutes.
For each case, output a single line containing 3 integers in this order: the total attractiveness value, the number of problems solved, the total penalty time. The 3 integers should be separated by a space.
2 300 10 10 10 10 10 10 10 10 10 10 10 1 2 3 4 5 6 7 8 9 10 300 10 301 301 301 301 301 301 301 301 301 301 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000