1029.
WHUgirls
时间限制 2000 ms
内存限制 128 MB
There are many pretty girls in Wuhan University, and as we know, every girl loves pretty clothes, so do they. One day some of them got a huge rectangular cloth and they want to cut it into small rectangular pieces to make scarves. But different girls like different style, and they voted each style a price wrote down on a list. They have a machine which can cut one cloth into exactly two smaller rectangular pieces horizontally or vertically, and ask you to use this machine to cut the original huge cloth into pieces appeared in the list. Girls wish to get the highest profit from the small pieces after cutting, so you need to find out a best cutting strategy. You are free to make as many scarves of a given style as you wish, or none if desired. Of course, the girls do not require you to use all the cloth.
输入数据
输出数据
Output the maximum sum of prices that you can get on a single line for each case.
Constrains
0 < T <= 20
0 <= N <= 10; 0 < X, Y <= 1000
0 < xi <= X; 0 < yi <= Y; 0 <= ci <= 1000
样例输入
复制
1
2 4 4
2 2 2
3 3 9 \n
· · \n
· · \n
· · \n