Nhân ngày sinh nhật, An muốn mời bạn bè đến dự tiệc tại nhà của cậu. Kế hoạch của cậu là mua một số lượng bánh ngọt để chia đều cho mọi người, nếu sau khi chia đều vẫn còn dư bánh thì cậu sẽ giữ lại chúng và ăn dần. An dự tính sẽ mời không quá \(N\) nguời bạn và mua không quá \(M\) chiếc bánh. Vì cậu rất thích bánh ngọt nên cậu muốn số lượng bánh dư không nhỏ hơn \(L\) để cậu có thể ăn thỏa thích, nhưng nếu ăn nhiều quá thì cậu sẽ tăng cân nên cậu muốn số lượng bánh dư không vượt quá \(R\). An muốn biết có bao nhiêu cách chọn số luợng người bạn có thể mời và số lượng bánh có thể mua sao cho thỏa mãn được mong muốn của cậu. Lưu ý, An phải mời ít nhất một người bạn và mua ít nhất một chiếc bánh, nếu số lượng bánh nhỏ hơn số lượng người bạn được mời thì những người đó sẽ không ăn bánh và An sẽ giữ lại hết số bánh và ăn dần (nhưng số lượng vẫn phải thỏa mãn điều kiện của cậu).
Input
- Gồm một dòng duy nhất chứa bốn số nguyên \(N, M, L\) và \(R\) \((1 \leq N, M \leq 10^{6}, \ 0 \leq L \leq R \leq N - 1)\).
Output
- In ra số lượng cách chọn thỏa mãn yêu cầu bài toán.
Scoring
- Subtask \(1\) (\(20\%\) số điểm): \(N, M \leq 1000\).
- Subtask \(2\) (\(20\%\) số điểm): \(R = 0\).
- Subtask \(3\) (\(20\%\) số điểm): \(R = N - 1\).
- Subtask \(4\) (\(40\%\) số điểm): không giới hạn gì thêm.
Example
Test 1
Input
5 5 2 4
Output
7
Note
Các cặp \((a, b)\) gồm \(a\) người bạn được mời và \(b\) chiếc bánh ngọt được mua thỏa mãn điều kiện của An là: \((3,2), (3,5), (4,2), (4,3), (5,2), (5,3), (5,4)\).
Test 2
Input
10 6 0 4
Output
51
Bình luận