864 . 超出預期

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

coding_pooh

User's AC Ratio

100.0% (11/11)

Submission's AC Ratio

68.8% (11/16)

Tags

ntucpc-speedrun1

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 分需要花費幾分鐘。

  • 1≤N≤105
  • 0≤si≤fi≤100
  • ∑i=1Nsi<K≤∑i=1Nfi
  • 1≤ci≤109
  • 對於所有輸入，保證答案一定是整數。

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
Submit
Back to Top