Q-4-16. 賺錢與罰款
泰山派的磨劍坊接了 \( n \) 筆訂單,每一筆訂單有需要的工時 \( t[i]\) 以及完工要求時間 \(d[i]\) ,如果在時間 \( x \) 的時後交貨就可以賺 \( d[i]-x \) 的錢,也就是說越早完成賺越多,超過時間完成的話,越晚賠越多。 磨劍坊每次只能做一件工作,所以要把這 \( n \) 筆訂單做一個排程,希望利潤最大,也就是賺最多錢,如果不可能賺錢就要賠最少。 泰山派掌門天門道長聽到之後,深怕會賠太多的錢而破產,請你幫忙找出最好的排程。
輸入格式
輸入的第一行是工作數 \( N\) 。 第二行有 \( N \) 個正整數,依序是各訂單所需時間 \(t[1]\) 、 \(t[2]\) 、…、 \(t[N]\) 。 第三行有 \( N \) 個非負整數,依序是各訂單的完工要求 \( d[1]\) 、 \(d[2]\) 、…、 \(d[N]\) ,相鄰以空白間隔。 \(N<1e5\) ,時間不超過 \( 1000\) ,完工要求不超過 \(1e8\) 。
輸出格式
最大利益。
範例輸入
5
4 1 5 2 2
2 5 5 3 1
範例輸出
-16
留言