Nobita

Điểm: 3,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Nguồn bài:

24-25 TS10 DANANG

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Javascript, Kotlin, Pascal, Python, Scratch

Nobita được Doraemon tặng một chiếc túi ma thuật có thể tăng sức mạnh của người dùng sau mỗi bước đi và một số bảo bối. Mỗi bảo bối có trọng lượng $C$ và giá trị phép thuật $H$ . Nobita chỉ có thể đi chuyển nếu chỉ số sức mạnh của mình lớn hơn hoặc bằng tổng trọng các bảo bối trong túi. Để thử tài của Nobita, Doraemon xếp các bảo bối trên một đường thẳng và yêu cầu Nobita di chuyển dọc theo đường thẳng. Nobita chỉ được phép tiến lên, chỉ có thể lấy bảo bối tại vị trí đang đứng cho vào túi hoặc không lấy. Mỗi bước đi, Nobita sẽ tăng thêm $X$ chỉ số sức mạnh. Ở mỗi lần thử thách có $M$ bảo bối, Nobita xuất phát tại vị trí bảo bối thứ nhất, chỉ số sức mạnh lúc này là $0$ và cái túi không chứa bảo bối nào. Mỗi bước đi Nobita sẽ tiến tới vị trí bảo bối tiếp theo. Hãy giúp Nobita lấy được các bảo bối có tổng giá trị phép thuật là cao nhất và đảm bảo cậu vẫn có thể đi chuyển bình thường. Biết rằng tổng giá trị phép thuật của bảo bối ở tất cả các lần thử thách không lớn hơn $10^{5}$ .

Hãy cho biết tổng giá trị phép thuật lớn nhất của các bảo bối mà Nobita lấy được ở mỗi lần thử thách là bao nhiêu.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên t (1≤t≤103) là số bộ test tương ứng với số lần thử thách. Các dòng tiếp theo tương ứng với t bộ test. Mỗi bộ test chứa dữ liệu như sau:
- Dòng đầu của mỗi bộ test chứa hai số nguyên dương $M$ ( $1 \leq M \leq 50$ ) và $X$ ( $1 \leq X \leq 10^{8}$ ).
- $M$ dòng tiếp theo mỗi dòng chứa hai số nguyên dương, dòng thứ $i$ chứa hai số nguyên dương $C_{i}$ ( $0 \leq C_{i} \leq 10^{8}$ ) và $H_{i}$ ( $1 \leq H_{i} \leq 10^{3}$ ).

Dữ liệu ra

Ghi ra $t$ số nguyên mỗi số nằm trên một dòng tương ứng với tổng giá trị phép thuật lớn nhất của bảo bối mà Nobita có được ở mỗi lần thử thách.

Ràng buộc

$1 \leq t \leq 10^{3}$
$1 \leq M \leq 50$
$1 \leq X \leq 10^{8}$
$0 \leq C_{i} \leq 10^{8}$
$1 \leq H_{i} \leq 10^{3}$
Tổng giá trị phép thuật ở tất cả các lần thử thách không lớn hơn $10^{5}$ .
30% số test có giá trị phép thuật bảo bối giảm dần, trọng lượng tăng dần.
30% số test có các bảo bối có trọng lượng bằng nhau và ( $t$ , $M < 10$ ).
40% số test tiếp theo không có giới hạn gì thêm.

Ví dụ

Input	Output	Giải thích
1 5 2 2 1 0 2 3 5 5 2 3 2	9	Ở vị trí thứ nhất: chỉ số sức mạnh là $0$ , không lấy bảo bối. Ở vị trí thứ hai: chỉ số sức mạnh là $2$ , lấy bảo bối có giá trị phép thuật $2$ . Ở vị trí thứ ba: chỉ số sức mạnh có là $4$ , lấy bảo bối có giá trị phép thuật là $5$ . Ở vị trí thứ tư: chỉ số sức mạnh có là $6$ , không lấy bảo bối. Ở vị trí thứ năm: chỉ số sức mạnh có là $8$ , lấy bảo bối có giá trị phép thuật $2$ . Tổng = $9$ .

Bình luận

Không có bình luận tại thời điểm này.