#466 무기 강화

출제자: lupin

문제

루핀은 픽셀 던전에서 무기를 강화하려고 한다.

처음에 무기의 강화 수치는 $X$ 이고, 강화 주문서의 수는 $\lfloor\sqrt{X}\rfloor$ 이다.

루핀은 다음 두 행동을 원하는 만큼 수행할 수 있다.

강화 주문서로 무기를 강화한다. 무기의 강화 수치는 현재 가지고 있는 강화 주문서의 수만큼 증가한다. 강화 주문서의 수는 변하지 않으며, 이 행동에는 시간이 만큼 걸린다.

A

트롤 대장장이에게 무기를 맡긴다. 대장장이는 루핀이 가지고 있던 강화 주문서를 모두 회수한 뒤, 현재 무기의 강화 수치가

c

라고 할 때

\lfloor\sqrt{c}\rfloor

만큼의 강화 주문서를 새로 만들어 준다. 이때 무기의 강화 수치는 변하지 않으며, 이 행동에는 시간이

B

만큼 걸린다.

루핀은 행동에 사용한 시간의 합이 $N$ 이하가 되도록 행동할 수 있다.

루핀이 만들 수 있는 무기의 강화 수치의 최댓값을 구하여라.

첫 번째 줄에 네 정수 $N, A, B, X$ 가 공백으로 구분되어 주어진다.

첫 번째 줄에 조건을 만족하도록 행동했을 때 만들 수 있는 무기 강화 수치의 최댓값을 출력한다.

$1 ≤ N ≤ 5\,000$

$1 ≤ A, B ≤ 10\,000$

$1 ≤ X ≤ 10^9$

#	점수	제한
1	100	-

입력

7 2 3 5

출력

11

[0]