Problem Description

Xiao Lan is a warehouse manager at a large logistics center. Today, the system issued an urgent task: all $N$ standard containers must be stored in the warehouse and assigned to $M$ shelves.

The shelves are numbered from left to right as $1, 2, \dots, M$. Because the distance for the automated robotic arm to deliver a container to different shelves varies, placing $1$ container onto shelf $i$ costs $i$ units of electricity.

The company requires that the total electricity cost of this storage task must lie within the closed interval $[L, R]$. At the same time, to avoid any single shelf bearing too much weight, Xiao Lan wants the shelf that holds the most containers to hold as few as possible.

Formally, you need to construct a non-negative integer sequence $a_1, a_2, \dots, a_M$, where $a_i$ denotes the number of containers placed on shelf $i$. The sequence must satisfy:

• All containers are assigned to shelves, i.e., $\sum_{i=1}^{M} a_i = N$.
• The total electricity cost satisfies $L \le \sum_{i=1}^{M} i \times a_i \le R$.

Among all valid assignment plans, output the minimum possible value of $\max(a_1, a_2, \dots, a_M)$. If no valid plan exists, output $-1$.

Input Format

The input consists of one line containing four integers $N, M, L, R$, representing the number of containers, the number of shelves, the lower bound of the total electricity cost, and the upper bound of the total electricity cost.

Output Format

Output one line containing one integer, the minimum possible value of $\max(a_i)$.

If no valid plan exists, output $-1$.

5 3 13 14

3

Hint

Sample Explanation

The following two plans both satisfy the total electricity cost constraint:

• $a_1 = 0, a_2 = 2, a_3 = 3$, with total electricity cost $0 \times 1 + 2 \times 2 + 3 \times 3 = 13$, and $\max(a_i) = 3$.
• $a_1 = 0, a_2 = 1, a_3 = 4$, with total electricity cost $0 \times 1 + 1 \times 2 + 4 \times 3 = 14$, and $\max(a_i) = 4$.

The first plan has a smaller maximum number of containers on any shelf. It can be proven that there is no valid plan with $\max(a_i)$ less than $3$, so the answer is $3$.

Constraints

For $40\%$ of the testdata, it is guaranteed that $N, M \le 40$.

For all testdata, it is guaranteed that $1 \le N, M \le 20000$ and $1 \le L \le R \le NM$.

Translated by ChatGPT 5