大赛将至，摆在你面前的是n道题目，第 i(1 ≤ i ≤ n) 道题目能提升 ai 点智力值，代码量为 bi KB，无聊值为 ci ，求至少提升m点智力值的情况下，所做题目代码量之和*无聊值之和最小为多少。
Input
第一行两个整数n，m(0<n<=400)
接下来n行每行三个整数，ai,bi,ci(0<bi,ci<=1000,0<ai<=800)。
0<m<=Σai<=800
Output
一个数，至少提升m点智力值的情况下，所做题目代码量之和*无聊值之和的最小值。
思路和求最小乘积生成树一样。。。不同的就是具体计算的时候是01背包而不是求mst。。。
大概就是将一个方案的b值之和看成X坐标，c值之和看成Y坐标。那么答案的方案肯定就在所有点组成的凸包的左下部分上。
直接丢题解网址了...http://www.51nod.com/onlineJudge/problemSolution.html#!problemId=1614
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstdlib>
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define d double
#define ld long double
const int maxn=; struct zs{int x,y;ll v;}f[maxn],a[maxn];
ll ANS,inf=1ll<<;int SMA;
int A[maxn];
int i,j,k,n,m; int ra,fh;char rx;
inline int read(){
rx=getchar(),ra=,fh=;
while(rx<''&&rx!='-')rx=getchar();
if(rx=='-')fh=-,rx=getchar();
while(rx>='')ra=ra*+rx-,rx=getchar();return ra*fh;
} //bool operator <(zs a,zs b){return a.v<b.v;}
zs operator +(zs a,zs b){return (zs){a.x+b.x,a.y+b.y,a.v+b.v};}
zs operator -(zs a,zs b){return (zs){a.x-b.x,a.y-b.y,a.v-b.v};}
inline int cross(zs a,zs b){return a.x*b.y-a.y*b.x;} inline void upd(zs &a,zs &b,zs &c){if(b.v+c.v<a.v)a=b+c;}
inline zs get(){
register int i,j,k;zs ans=(zs){,,inf};
for(i=;i<=SMA;i++)f[i].v=inf;
for(i=;i<=n;i++)
for(j=SMA,k=j-A[i];j>=A[i];j--,k--)upd(f[j],f[k],a[i]);
for(j=m;j<=SMA;j++){
if(f[j].v<ans.v)ans=f[j];
if(1ll*f[j].x*f[j].y<ANS)ANS=1ll*f[j].x*f[j].y;
}
return ans;
}
inline void run(zs A,zs B){
for(register int i=;i<=n;i++)a[i].v=a[i].x*(A.y-B.y)+a[i].y*(B.x-A.x);
zs C=get();
if(cross(B-A,C-A)>=)return;
run(A,C),run(C,B);
} int main(){
n=read(),m=read();
for(i=;i<=n;i++)A[i]=read(),a[i].x=read(),a[i].y=read(),SMA+=A[i]; ANS=inf;
for(i=;i<=n;i++)a[i].v=a[i].x;zs A=get();
for(i=;i<=n;i++)a[i].v=a[i].y;zs B=get();//printf("sty:%d (%d,%d) stx:%d (%d,%d)\n",A.v,A.x,A.y,B.v,B.x,B.y);
//printf("ANS:%lld\n",ANS);
run(A,B);
printf("%lld\n",ANS);
}