Nhào Lộn Bò

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Nông dân John muốn các con bò xếp thành các tháp cân bằng. Một tháp được gọi là cân bằng khi mỗi con bò đỡ một con bò khác phải có cân nặng lớn hơn con bò phía trên ít nhất $K$ đơn vị.

Có $N$ loại cân nặng khác nhau, loại thứ $i$ có cân nặng $w_{i}$ và số lượng $a_{i}$ con bò. Các con bò được xếp vào tối đa $M$ tháp. Hãy tìm số lượng con bò tối đa có thể tham gia vào các tháp.

Dữ liệu vào

Dòng $1$ : Ba số nguyên $N$ , $M$ , $K$ ( $1 \leq N \leq 2 \cdot 10^{5}$ ; $1 \leq M \leq 10^{9}$ ; $1 \leq K \leq 10^{9}$ ).
$N$ dòng tiếp theo: Mỗi dòng gồm hai số nguyên $w_{i}$ và $a_{i}$ ( $1 \leq w_{i}, a_{i} \leq 10^{9}$ ), các $w_{i}$ phân biệt đôi một.

Dữ liệu ra

In ra một số nguyên — số lượng con bò tối đa có thể tham gia vào các tháp cân bằng.

Ràng buộc

Các test $2$ - $4$ : $N \leq 10$ , $a_{i} \leq 10$ , $M \leq 10$ .
Các test $5$ - $8$ : $N \leq 1000$ , $a_{i} \leq 1000$ .
Các test $9$ - $17$ : Không có ràng buộc thêm.

Ví dụ

Input	Output	Giải thích
3 5 2 9 4 7 6 5 5	14	Có 3 loại bò: nặng 9 (4 con), 7 (6 con), 5 (5 con). Với $K = 2$ và tối đa 5 tháp, ta có thể xếp 14 con bò.
3 5 3 5 5 7 6 9 4	9	Với $K = 3$ , chỉ bò nặng 5 và 9 có thể xếp cùng tháp (chênh 4 >= 3), nhưng 7 với 5 hoặc 9 chênh chỉ 2 < 3 nên bò nặng 7 chỉ đứng 1 tầng.

Bình luận

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