674 . RPG 遊戲

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (3/3)

Tags

apcsc apcsc-ds

Description

小風正在玩 RPG 遊戲，這個遊戲需要玩家們藉由學習攻擊與防守的能力值來獲取技能，遊戲中共有 $N$ 個技能，每個技能都必須要至少有 $a_i$ 的攻擊力以及 $b_i$ 的防守力才能夠習得，小風每一秒鐘只能讓某個能力值提升一點，且一開始攻擊力以及防守力都是 $0$，請問他至少要花費多少時間才能夠習得其中的 $K$ 個技能呢？

Input Format

輸入第一行有兩個正整數 $N, K (1 \leq K \leq N \leq 10^ 6)$，代表技能的數量以及想學習的技能數。
接下來共有 $N$ 行，第 $i$ 行有兩個正整數 $a_i, b_i (1 \leq a_i, b_i \leq 10^ 6)$，代表學習這個技能所需要的最小攻擊力與防守力。

Output Format

請輸出一個正整數，表示至少需要花費多久時間才能夠達成目標。

Sample Input 1

5 3
5 5
8 1
2 9
1 7
5 3

Sample Output 1

12

Sample Input 2

5 3
3 9
1 10
7 5
10 3
5 8

Sample Output 2

15

Hints

Problem Source

TIOJ

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 65536 1 2
1 3000 65536 65536 1 2
2 3000 65536 65536 2
3 3000 65536 65536 2
4 3000 65536 65536 2
5 3000 65536 65536 2
6 3000 65536 65536 2
7 3000 65536 65536 2
8 3000 65536 65536 2
9 3000 65536 65536 2
10 3000 65536 65536 2
11 3000 65536 65536 2
Submit
Back to Top