Trò chơi (HSG9 HN 2024)

Điểm: 1200 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 1G

Input: TROCHOI.inp

Output: TROCHOI.out

Tác giả:

NgVanMinh

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)

Output (TROCHOI.out)

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

Không có bình luận nào.