Nathan 是一個成績優異的學生，從小到大上過的每一門課，他都獲得了非常好的成績，老師們都稱讚他是一個遠遠超出他們預期的學生。

這個學期，Nathan 上了一門叫作「進階區間資料結構」的課程，不幸的是，由於 Nathan 這個學期太忙了，他沒有時間好好做這門課的作業，因此成績不太理想。幸運的是，教授願意提供他補救方案：這門課共有 $N$ 個作業，Nathan 在第 $i$ 份作業本來獲得的成績是 $s_i$，這份作業的滿分是 $f_i$，Nathan 可以透過提交一份關於這份作業內容的筆記來提高他的成績，精打細算的 Nathan 知道，他只要多花 $c_i$ 分鐘就能讓這份作業的分數增加 1 分。Nathan 只要花足夠多的時間就可以在一份作業獲得任意多的分數，但 Nathan 最多只能把第 $i$ 份作業的分數提高到 $f_i$。

即便放暑假了，Nathan 還是很忙，所以他偷偷打聽到只要他 $N$ 份作業的總分 $\geq K$，他就可以獲得 A+，請告訴他至少要再花幾分鐘才能得到 A+。