题意： n个人吃披萨，总共有两种披萨，每种披萨都是有S块，给出每个人要吃的块数，吃第一种披萨能获得的happy值，吃第二种披萨能获得的happy值，问你，在购买的披萨数最少的情况下能获得的最大的总的happy值是多少（披萨可以买任意多个，吃不完也行 2333333）

Examples

Input

3 12 3 5 7 4 6 7 5 9 5

Output

84

Input

6 10 7 4 7 5 8 8 12 5 8 6 11 6 3 3 7 5 9 6

Output

314 思路：首先肯定是每个人都吃happy值更大的那一种披萨最优，但是有一个问题，可能会多出一点零头，那么我们记为sum1和sum2。 　　　如果sum1+sum2>S，那么这些零头肯定是要买两个披萨的，不如就各买各的，那么答案就是ans； 　　　但是如果sum1+sum2<=S，那么就要一起买一个披萨了，这样的话就用ans-min（让买第一种披萨的去买第二种的差值， 　　　让买第二种披萨的去买第一种的差值）， 　　　 这样算出来的结果就是答案了。 　　 （用结构体保存一下a，b，差值，然后按差值从小到大来排序，肯定是让差值小的最后买这样才最划算，因为如果要买另外一 　　　　个这样损失最小） 　　　for(int i=0;i
    
      #include
     
       #include
      
        using namespace std; const int maxn=1e5+5; struct node{
         long long s,a,b,c; }t1[maxn],t2[maxn]; bool cmp(node x,node y){
         return x.c
       
        >n>>S;     for(int i=0;i
        
         >x>>y>>z;         if(y>z){
                 t1[n1].s=x;             t1[n1].a=y;             t1[n1].b=z;             t1[n1].c=y-z;             ans+=t1[n1].a*t1[n1].s;             sum1=(sum1+t1[n1].s)%S;             n1++;         }         else {
                 t2[n2].s=x;             t2[n2].a=y;             t2[n2].b=z;             t2[n2].c=z-y;             ans+=t2[n2].b*t2[n2].s;             sum2=(sum2+t2[n2].s)%S;             n2++;         }     }     if(sum1+sum2>S){
             cout<
         
          <