TopCoder

User's AC Ratio

100.0% (11/11)

Submission's AC Ratio

68.8% (11/16)

Tags

Description

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

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

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

Input Format

第一行有兩個整數 N,K,分別代表作業的份數與 Nathan 的總分需要達到幾分才能獲得 A+。

接下來有 N 行,其中第 i 行包含 3 個整數 si,fi,ci,分別代表 Nathan 本來在第 i 份作業得到的分數、這份作業的滿分,以及 Nathan 多拿到 1 分需要花費幾分鐘。

  • 1N105
  • 0sifi100
  • i=1Nsi<Ki=1Nfi
  • 1ci109
  • 對於所有輸入,保證答案一定是整數。

Output Format

輸出一個整數,代表 Nathan 要獲得 A+ 需要花幾分鐘在補救方案上。

Sample Input 1

3 20
5 10 3
6 10 1
4 15 2

Sample Output 1

6

Sample Input 2

3 68
18 20 2
45 50 2
0 0 1

Sample Output 2

10

Sample Input 3

1 100
0 100 1000000000

Sample Output 3

100000000000

Sample Input 4

10 94
0 3 18
13 18 19
0 0 15
14 18 11
6 7 20
3 6 17
10 18 11
14 15 8
18 20 17
10 10 8

Sample Output 4

63

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~3 範例測資 0
2 0~19 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 1 2
3 1000 524288 65536 1 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2