当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。

请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

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.

The first line of input consists of an integer T, indicating the number of test cases.

The first line of each case consists of three integers N, X, Y, N indicating there are N kinds of rectangular that you can cut in and made to scarves; X, Y indicating the dimension of the original cloth. The next N lines, each line consists of two integers, xi, yi, ci, indicating the dimension and the price of the ith rectangular piece cloth you can cut in.

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

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

9

共提交 12 次

通过率 50.0%

时间上限 | 内存上限 |

2000 MS | 128 MB |

登陆或注册以提交代码