切割矩形（rec.pas/c/cpp）

题目描述

给定一个X*Y的大矩形，你可以将该矩形任意切割趁若干的小矩形。不同的小矩形有着不同的价值。现在让你将该矩形切割，使小矩形的价值总和最大。



输入格式

第一行包含N、X、Y三个整数，表示一共给出N个小矩形和大矩形的大小X*Y

第二行到第N+1行，每行包含xi，yi，vi三个整数，表示xi*yi的矩形价值为vi

输出格式

输出只包括一行，即最大价值。



输入样例1：

1 3 3

2 2 5



输出样例1：

5





输入样例2：

2 3 3

2 2 10

1 1 2



输出样例：2

20





数据范围：

0<=X，Y<=1000

N<=20- cut the rectangle (rec.pas/c/cpp)





Title Descr iption

Given a X* Y of the large rectangle, the rectangle you can take advantage of any number of cutting a small rectangle. Different small rectangle has a different value. Now you cut the rectangle, so that the sum of the maximum value of a small rectangle.



Input format

The first line contains N, X, Y 3 integers that total N is given a small rectangle and large rectangle the size of the X* Y

N 1 second line to line, each line contains xi, yi, vi three integers that xi* yi rectangle value vi

Output format

　　Output only line, that the greatest value.



Input Sample 1:

133

225



Output Sample 1:

5





Input Sample 2:

233

2210

112



Sample output: 2

20





Data range:

0 <= X, Y <= 1000

N <= 20