4509 . 蔡摩卡與背包
TopCoder
Description
眾所皆知，一二的學術長雷夢有一隻可愛的貓咪，叫做蔡摩卡。蔡摩卡聰明到會拯救被仙人掌攻擊的學長（詳見去年小社賽pF）、躲入紙箱（詳見去年考幹題）、找女朋友（詳見pF）。不過，蔡摩卡最喜歡的還是雷夢了，總喜歡一直纏在他身邊磨蹭(?)。
但是到了最近，由於雷夢忙著準備去台大資工炸魚，漸漸開始塑膠蔡摩卡了。生氣的蔡摩卡為了引起雷夢的注意，決定要來搞破壞。他走到了雷夢準備送給叮叮的一堆名牌背包旁邊，舉起了他尖銳的爪子......
目睹這一切的雷夢，當然不能讓蔡魔卡破壞他辛辛苦苦買來的背包。但是，蔡摩卡動作實在是太快了，立刻躲到了箱子當中。直到過了好一番功夫之後，雷夢才終於把蔡摩卡抓到門外。但他知道，蔡摩卡很快就會破門而入繼續搞破壞的，因此，他要趕快把背包都收起來！
已知雷夢總共有$n$個要送給叮叮的背包，而每個包包的價格分別是 $v_i$ 。另外，雷夢搶救每個背包分別需要花費$t_i$秒鐘，且他不可以一次搶救兩個包包。另外，蔡摩卡會在$m$秒鐘之後破門而入開始亂抓一通，導致來不及被搶救的背包直接被原地分屍。
身為資訊電神的雷夢，立馬想到了一個方法，可以判斷他應該搶救哪幾個背包才能讓他的損失最小。但是，他正忙著擋住蔡摩卡破門，沒有手寫程式。因此它請你幫忙，想請問他應該在搶救完之後，蔡摩卡破壞的背包價值最低可以多少？
Input Format
$n$ $m$
$v_1$ $v_2$ $v_3$ ... $v_n$
$t_1$ $t_2$ $t_3$ ... $t_n$
測資範圍：
subtask 1(70\%): $n, m < 10^3$
subtask 2(30\%): $n, m < 10^7$
另外對於所有測資，保證 $n \times m < 10^7, 0 < v_i < 10^6$，且$t_i, v_i$皆為int範圍。
Output Format
請輸出蔡摩卡破壞的背包價值最低可以多少？
Sample Input 1
30 50 60
3 4 5
Sample Output 1
Sample Input 2
1000000 1000000 1000000 1000000 1000000
2 2 2 2 2
Sample Output 2
Hints
如果一直TLE的話，可以注意每個subtask的範圍喔！
提示：要用到簡報最後面寫的某個技巧
蛤？你問我為什麼雷夢有錢買那麼多那麼貴的背包？
他可是全建北電資歷屆最強的學術長誒，光圖靈獎就不知道得過幾次了w
Problem Source
111年小社賽pD
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~11 | n, m < 103 | 70 |
| 3 | 0~21 | n, m < 107 | 30 |