Nộp bài
Điểm:
1200 (thành phần)
Thời gian:
1.0s
Bộ nhớ:
1G
Input:
TROCHOI.inp
Output:
TROCHOI.out
Tác giả:
Dạng bài
Bạn có 1 nhân vật cần được tăng chỉ số sức mạnh. Nhân vật của bạn có N kĩ năng được đánh thứ tự từ 1 đến N. Kĩ năng thứ i (1 \le i \le N) có 2 loại chỉ số tăng tiến là s_i và e_i. Trong lần đầu tiên tăng cấp kĩ năng thứ i, nhân vật của bạn được (s_i+e_i) chỉ số sức mạnh. Trong các lần tiếp theo tăng cấp kĩ năng thứ i, nhân vật của bạn chỉ nhận được thêm e_i chỉ số sức mạnh. Bạn có thể tăng cấp 1 kĩ năng bất kì không giới hạn số lần. Trò chơi diễn ra trong M phút, mỗi phút nhân vật của bạn nhận được 1 lần tăng cấp kĩ năng.
Yêu cầu: Hãy tìm chỉ số sức mạnh lớn nhất mà nhân vật của bạn có thể đạt được sau M phút chơi.
Input, Output và Scoring
Input (TROCHOI.inp
)
- Dòng đầu tiên chứa 2 số nguyên dương N và M (1 \le N \le 10^5; 1 \le M \le 10^9).
- Dòng thứ i trong N dòng tiếp theo chứa 2 số nguyên dương s_i và e_i (s_i \le 10^9, e_i \le 10^9).
Output (TROCHOI.out
)
- Một số nguyên duy nhất là chỉ số sức mạnh lớn nhất mà nhân vật của bạn có thể đạt được.
Scoring
- Subtask 1 (40\%): m = 2
- Subtask 2 (40\%): m \le 100
- Subtask 3 (20\%): Không có ràng buộc gì thêm.
Test
Input (TROCHOI.inp
)
3 4
2 2
2 5
5 1
Output (TROCHOI.out
)
23
Note
Cách nâng cấp tối ưu nhất là:
- Nâng cấp 3 lần kĩ năng 2.
- Nâng cấp 1 lần kĩ năng 3.
Tổng chỉ số sức mạnh nhận được sẽ là (2+5)+5+5+(5+1) = 23
Bình luận