Nhà _minhduc có bán những quả bóng ~~cười~~ bay với đủ loại màu sắc rực rỡ, để trang trí cho lớp nhân ngày Cá tháng Tư, shiba quyết định sẽ đến mua bóng ở đây.

Do nhà _minhduc đang hỏng máy bơm, nên shiba phải tự thổi bóng. Quả bóng thứ \(i\) có giá tiền là \(a_{i}\), shiba cần thổi bóng đến đúng kích thước là \(b_{i}\). shiba chỉ có thể thổi được bóng đến kích thước tối đa là \(m\). Nếu không thổi được một quả bóng, shiba có thể đi thuê bơm, giá tiền thuê bơm cho một quả bóng có kích thước cần thổi lớn hơn kích thước cậu ấy có thể thổi là \(b_{i}-m\). Ban đầu, shiba có số tiền là \(k\).

Yêu cầu: Hỏi Nguyên có thể mua và trang trí được tối đa bao nhiêu quả bóng?

Input

• Dòng thứ nhất chứa ba số nguyên dương \(n,m,k\) (\(n \le 10^5, m \le 10^9, k \le 10^{14}\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a_{i}, b_{i}\) (\(a_{i}, b_{i} \le 10^9\)).

Output

• In ra một số nguyên duy nhất là số quả bóng shiba có thể mua và trang trí.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(b_{i} \le m\).
• Subtask \(2\) (\(60\%\) số điểm): không có ràng buộc gì thêm.

Example

5 10 15
11 22
1 2
1 3
1 4
1 5

4

Số Chính Phương là là số tự nhiên có căn bậc hai là một số tự nhiên, hay nói cách khác, số chính phương bằng bình phương của một số nguyên không âm.

Ví dụ về các Số Chính Phương đầu tiên: \(0,1,4,9,16,...\)

Yêu Cầu: Cho một số nguyên dương \(N\). Hãy đếm số cặp \((x,y)\) thỏa mãn tất cả các điều kiện sau:

• \(1 \le x,y \le N\).
• \(x^2-y\) là số chính phương.

Vì kết quả có thể quá lớn, hãy in ra đáp án bài toán sau khi chia lấy dư cho \(998244353\).

Input

• Chứa một số nguyên dương \(N\) duy nhất \((1 \le N \le 10^{12})\).

Output

• In ra kết quả bài toán sau khi chia lấy dư cho \(998244353\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1 \le N \le 5000\).
• Subtask \(2\) (\(30\%\) số điểm): \(5000 < N \le 10^6\).
• Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

3

2

_minhduc là một người rất thích ăn bánh quy nên shiba đã tập nướng bánh quy cho _minhduc ăn 😃

shiba cần nướng \(N\) cái bánh quy cho _minhduc ăn.

Ban đầu shiba có \(S = 0\) cái bánh quy, và năng suất lúc bắt đầu nướng bánh của cậu là \(W = 1\) (bánh / phút).

Với mỗi lần thao tác thì cậu có thể chọn một trong hai thao tác sau:

• Tốn \(1\) phút để nướng bánh quy với công suất hiện tại: \(S = S + W\).
• Tốn \(T\) phút để ăn hết lượng bánh đang có và thay đổi công suất: \(W = S\), sau đó \(S = 0\).

Yêu Cầu: Bạn hãy tìm cho shiba thời gian ít nhất có thể để nướng được ít nhất \(N\) cái bánh, hay nói cách khác hãy tìm thời gian ngắn nhất để \(S \ge N\).

Input

Nhập từ Bàn Phím hai số nguyên không âm lần lượt là \(N\) và \(T\) \((1 \le N \le 10^{12}, 0 \le T \le 10^{12})\).

Output

In ra Màn Hình thời gian ít nhất thỏa mãn yêu cầu đề bài với đơn vị phút.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): Có \(N,T \le 10^6\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

8 1

7

Minh Đức sau khi tỏ tình thất bại đã trở thành \(1\) sadboiz chính hiệu, anh ta lúc nào cũng như \(1\) người thất thần. Để anh ta mau chóng quên đi "người xém trở thành người yêu của _minhduc nhưng không thành" thì thầy Tiến đã ra \(1\) đề bài ngắn gọn như sau:

• Bạn có một cái cây \(n\) đỉnh và bạn phải điền số \([1..m]\) vô các đỉnh sao cho mọi đỉnh liền kề thì giá trị tuyệt đối hiệu của \(2\) đỉnh \(\ge\) \(k\).
• Yêu cầu bạn hãy đếm số cách điền số vào cây sao cho thoả mãn điều kiện trên

Input

• Dòng đầu tiên gồm \(1\) số nguyên dương \(t\) là số test (\(1 \le t \le 10\)).
• \(t\) bộ test tiếp theo mỗi test theo định dạng sau:
• Dòng đầu gồm \(3\) số nguyên dương \(n,m,k\) (\(1 \le n,k \le 100\),\(1 \le m \le 10^9\)).
• \(n-1\) dòng tiếp gồm \(2\) số nguyên dương \(u,v\) \(-\) có một cạnh nối giữa \(2\) đỉnh \(u,v\)

Output

• Với mỗi bộ test bạn cần in ra trên một dòng: số cách đếm theo yêu cầu đề bài, do kết quả có thể rất lớn nên bạn hãy chia lấy dư cho \(10^9+7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1 \le m \le 100\),
• Subtask \(2\) (\(20\%\) số điểm): \(1 \le m \le 10^5\),
• Subtask \(3\) (\(20\%\) số điểm): \(1 \le m \le 10^9\), đỉnh \(1\) nối trực tiếp với \(n-1\) đỉnh khác.
• Subtask \(4\) (\(20\%\) số điểm): \(1 \le m \le 10^9\), đỉnh \(i\) nối với đỉnh \(i+1\), với \(i\) từ \(1\) đến \(n-1\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

2
2 2 0
1 2
3 3 2
1 3
1 2

4
2