Співбесіди

Вхідні дані

Перший рядок містить одне ціле число $t$ (1 \le t \le 10^4) — кількість наборів вхідних даних.

Кожен набір вхідних даних складається з одного рядка, що містить чотири цілі числа p, x, y, z (1 \le p,x,y,z \le 10^9) — кількість кандидатів, які подають заявки до MathModel Labs, кількість інтерв'юерів, максимальна кількість співбесід, які може відвідати один інтерв'юер за день, і кількість інтерв'юерів, необхідних для співбесіди з одним кандидатом.

Вихідні дані

Виведіть мінімальну кількість днів, необхідних для проведення співбесід з усіма $p$ кандидатами, або виведіть $-1$, якщо це неможливо.

Приклади

Примітка

У першому наборі вхідних даних процес може відбуватися наступним чином лише в День $1$:

1. Інтерв'юери $1$ та $2$ проводять співбесіду з Кандидатом $1$.

2. Інтерв'юери $1$ та $3$ проводять співбесіду з Кандидатом $2$.

3. Інтерв'юери $2$ та $3$ проводять співбесіду з Кандидатом $3$.

Ця організація передбачає двох інтерв'юерів на зустріч, одного кандидата та максимальну кількість двох співбесід на день для інтерв'юера.

У другому наборі вхідних даних кожен інтерв'юер може відвідати співбесіди з загалом $2$ кандидатами, тому процес найму завершується за $5$ днів.

У третьому наборі вхідних даних кожен інтерв'юер може відвідати співбесіди з загалом $1$ кандидатом, тому процес найму завершується за $9$ днів.

У четвертому наборі вхідних даних кожен інтерв'юер може відвідати $2$ співбесіди на день, і кожна співбесіда вимагає $3$ інтерв'юерів. Один дійсний графік виглядає так:

1. День $1$: всі $3$ інтерв'юери проводять співбесіду з Кандидатом $1$, потім всі $3$ інтерв'юери проводять співбесіду з Кандидатом $2$.

2. День $2$: всі $3$ інтерв'юери проводять співбесіду з Кандидатом $3$, потім всі $3$ інтерв'юери проводять співбесіду з Кандидатом $4$.

3. $\dots$

4. День $10$: всі $3$ інтерв'юери проводять співбесіду з Кандидатом $19$, потім всі $3$ інтерв'юери проводять співбесіду з Кандидатом $20$.

Отже, для завершення потрібно $10$ днів.

У п'ятому наборі вхідних даних можна показати, що неможливо провести співбесіди з усіма кандидатами.

Оцінювання

1. Підзадача $1$ ($20$ балів) : (1 \le p,x,y,z \le 10)

2. Підзадача $2$ ($30$ балів) : (y=1)

3. Підзадача $3$ ($100$ балів) : Без додаткових обмежень