Друзі Зеника
Limits: 2 sec., 256 MiB
У Зеника є \(m\) друзів, яких він дуже поважає. Він вирішив купити деяку кількість яблук і розділити їх між собою і друзями. Зеник знає, що для того аби друзі і його поважали, він має дати кожному з них якомога більшу кількість яблук. Крім того, усі друзі повинні отримати однакову кількість яблук. Ті яблука, які залишаться, він забере собі. Іншими словами, якщо в Зеника є \(x\) яблук, то він віддасть кожному другові по \(x\) div \(m\) яблук, а собі візьме решту — \(x\) mod \(m\) яблук.
Зараз Зенику потрібно вирішити, скільки яблук йому купити початково. Він вирішив, що кількість яблук, яку він отримає, має бути в проміжку \([a, b]\) (границі включно). Окрім цього, у нього недостатньо грошей, щоб купити більше ніж \(n\) яблук. (Зауважте, що він може купити 0 яблук.)
Допоможіть Зенику порахувати кількість варіантів покупки, які б задовольняли його вимоги.
Input
У єдиному рядку задано чотири цілих числа \(n\), \(m\), \(a\) та \(b\) — максимальну кількість яблук, яку може купити Зеник, кількість друзів, найменшу та найбільшу кількість яблук, яку може отримати Зеник.
Output
У єдиному рядку виведіть одне ціле число — відповідь на задачу.
Constraints
\(1 \le n, m \le 10^9\),
\(0 \le a \le b \le 10^9\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 7 4 1 5 | 6 |
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|