1018 - Two thieves

Time Limit : 3 Second

Memory Limit : 128 MB

Submission: 394

Solved: 79

Description
There are two thieves, both of them have a bag whose capacity is CAP (1<= CAP <= 512). And there are N (N <= 128) diamonds, each of them have a weight w and a value v (1 <= w,v <= 512). The consecutive diamonds can not be put in the same bag.
The two greedy thieves want to earn as mush value as possible. Can you help them to solve this tough work?
Input
There are multiply test cases.
The first line: three integers N, CAP1, CAP2;
The following N lines: each line with two integers w, v.
Output
The total value of the diamonds which have been stolen by the two thieves.
sample input
3 9 19
4 5
7 10
8 9
sample output
24
hint
source
dupeng
© 2015 HUST ACMICPC TEAM. All Right Reserved.