$\text{[Problem?Discription]}$

來源：洛谷。侵權則刪。

$\text{[Analysis]}$

貪心。優先運送樓層高的貨物，在能裝下的情況下盡量多裝。

因為運送貨物的代價僅和最高樓層的貨物有關，假設一次運送貨物時的最高樓層為 $h$，那么無論你剩下的貨物樓層高還是低，代價都是 $h$ 是固定的。

既然這樣，我們應該優先把盡量高的貨物都運送上去，剩下來的都是高度低的貨物，后面的代價會減小。

排序后，從樓層高的貨物開始裝填，能裝下就裝下。注意處理特殊情況：即電梯剩余空間只有 $1$，但貪心需要裝大小為 $2$ 的貨物時是裝不下的。但是既然電梯空間還有剩余，就不應該浪費，應該找到下一個大小為 $1$ 的貨物。

指針來回的挪動可能會導致 T，因此按 $w=1,2$ 把貨物分成兩批，分別用一個指針來維護。這樣可以保證時間復雜度為 $O(n)$。

總時間復雜度 $O(n\log n)$，主要瓶頸在于排序。

但是，并沒有做完!

這道題對代碼能力的要求還是很高的。代碼中有非常多容易出錯的地方！相信這個貪心還是很多選手都能想到的，但是能不能寫出來也是一個重要的問題。

具體的細節看代碼中的注釋。

$\text{Code}$

const int N=1e5+100;struct Marchandise{int amount,high;Marchandise(int a=0,int h=0){amount=a;high=h;}bool operator < (const Marchandise &c) const{return high>c.high;}
}a[N],b[N];//w=1,2 的分別存 int n,r1,r2;
ll lim,ans;int OZDY(){n=read();lim=read();ans=r1=r2=0;for(int i=1;i<=n;i++){int c=read(),w=read(),f=read();if (w==1) a[++r1]=(Marchandise){c,f};else b[++r2]=(Marchandise){c,f};}sort(a+1,a+r1+1);sort(b+1,b+r2+1);a[r1+1]=(Marchandise){0,0};b[r2+1]=(Marchandise){0,0};//沒有這兩行應該也沒問題int l1=1,l2=1;ll remain=lim;while (l1<=r1&&l2<=r2){if (b[l2].high>=a[l1].high&&remain!=1){//樓層高的優先int tmp=(int)min((ll)b[l2].amount,remain>>1);if (remain==lim) ans+=b[l2].high;remain-=(tmp<<1);b[l2].amount-=tmp;//到這一行，remain 和 amount 至少一個被清零。if (!b[l2].amount){l2++;if (remain==0) remain=lim;continue;//注意一定要 continue，不然可能就直接進入下一個 if，開始裝填 l2+1 了，但 l2+1 不一定是下一個裝填的貨物（可能是 l1，但不可能是 l2+2）。}if (l2>r2) break;if (remain==0){ans+=1ll*b[l2].high*((b[l2].amount<<1)/lim);//注意括號b[l2].amount%=(lim>>1);if (!b[l2].amount){l2++;remain=lim;}else{ans+=b[l2].high;remain=lim-(b[l2].amount<<1);l2++;}}}else{if (remain==1){a[l1].amount--;remain=lim;//這句話別忘了if (!a[l1].amount) l1++;continue;}//電梯剩余空間為 1 特殊處理int tmp=(int)min((ll)a[l1].amount,remain);if (remain==lim) ans+=a[l1].high;remain-=tmp;a[l1].amount-=tmp;if (!a[l1].amount){l1++;if (remain==0) remain=lim;//都恰好拿完 continue;}if (l1>r1) break;if (remain==0){ans+=1ll*a[l1].high*(a[l1].amount/lim);a[l1].amount%=lim;if (!a[l1].amount){l1++;remain=lim;}else{ans+=a[l1].high;remain=lim-a[l1].amount;l1++;}}}} //每進入循環一次，要么 l1 加一要么 l2 加一，保證時間復雜度if (remain==0) remain=lim; //注意維護關鍵變量（其實出循環后 remain 應該不會為 0，但是維護一下以免出亂子，反正不費事）while (l2<=r2){if (remain==1) remain=lim;//只剩下 w=2 的貨物了，剩余的 1 空間沒用了int tmp=(int)min((ll)b[l2].amount,remain>>1);//下面的語句幾乎就是復制過來的。if (remain==lim) ans+=b[l2].high;remain-=(tmp<<1);b[l2].amount-=tmp;if (!b[l2].amount) l2++;//這里不需要 continue 了，因為下一個裝的一定是 l2+1if (l2>r2) break;if (remain==0){ans+=1ll*b[l2].high*((b[l2].amount<<1)/lim);b[l2].amount%=(lim>>1);if (!b[l2].amount){l2++;remain=lim;}else{ans+=b[l2].high;remain=lim-(b[l2].amount<<1);l2++;}}}while (l1<=r1){int tmp=(int)min((ll)a[l1].amount,remain);if (remain==lim) ans+=a[l1].high;remain-=tmp;a[l1].amount-=tmp;if (!a[l1].amount) l1++;if (l1>r1) break; if (remain==0){ans+=1ll*a[l1].high*(a[l1].amount/lim);a[l1].amount%=lim;if (!a[l1].amount){l1++;remain=lim;}else{ans+=a[l1].high;remain=lim-a[l1].amount;l1++;}}}//雖然代碼看著很長，但是最主要的四段幾乎就是復制粘貼，修改一些小細節printf("%lld\n",ans);return n;
}int main(){int T=read();while (T--) OZDY();return 0;
}