루핀은 픽셀 던전에서 무기를 강화하려고 한다.
처음에 무기의 강화 수치는 XXX이고, 강화 주문서의 수는 ⌊X⌋\lfloor\sqrt{X}\rfloor⌊X⌋이다.
루핀은 다음 두 행동을 원하는 만큼 수행할 수 있다.
루핀은 행동에 사용한 시간의 합이 NNN 이하가 되도록 행동할 수 있다.
루핀이 만들 수 있는 무기의 강화 수치의 최댓값을 구하여라.
첫 번째 줄에 네 정수 N,A,B,XN, A, B, XN,A,B,X가 공백으로 구분되어 주어진다.
첫 번째 줄에 조건을 만족하도록 행동했을 때 만들 수 있는 무기 강화 수치의 최댓값을 출력한다.
1≤N≤5 0001 ≤ N ≤ 5\,0001≤N≤5000
1≤A,B≤10 0001 ≤ A, B ≤ 10\,0001≤A,B≤10000
1≤X≤1091 ≤ X ≤ 10^91≤X≤109
