Nhào Lộn Bò

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\le N\le 2·{10}^5$; $1\le M\le {10}^9$; $1\le K\le {10}^9$).
• $N$ dòng tiếp theo: Mỗi dòng gồm hai số nguyên $w_i$ và $a_i$ ($1\le w_i,a_i\le {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\le 10$, $a_i\le 10$, $M\le 10$.
• Các test $5$-$8$: $N\le 1000$, $a_i\le 1000$.
• Các test $9$-$17$: Không có ràng buộc thêm.

Ví dụ