구운 과자

면접 대비

시간 제한1초메모리 제한1024 MB

요약

예산 S유로와 두 종류 컵케이크의 재료비, 이익이 주어질 때 예산 안에서 만들 수 있는 개수 조합의 최대 이익을 구합니다.

문제

Ugnė는 학교 바자회에 내놓을 두 종류의 컵케이크를 굽기로 했다.

어머니의 비밀 레시피 덕분에 필요한 재료의 양은 알고 있다. 그녀의 계산에 따르면 첫 번째 종류 컵케이크 하나의 재료비는 a 유로이고, 두 번째 종류는 b 유로다.

첫 번째 종류 컵케이크를 하나 팔면 A 유로의 이익이 남고, 두 번째 종류는 하나당 B 유로의 이익이 남는다. 다만 제과 일을 시작하기 전에 빵을 구울 재료를 먼저 마련해야 한다.

Ugnė는 어머니가 재료 구입용으로 S 유로를 준다면, 컵케이크를 팔아서 얻을 수 있는 최대 이익이 얼마인지 궁금해한다. 그녀는 구운 컵케이크를 모두 팔 수 있다고 확신한다.

첫 번째 줄에는 Ugnė가 컵케이크를 만드는 데 쓸 수 있는 돈 S가 정수로 주어진다. 컵케이크를 팔아 번 돈으로 새 재료를 살 수는 없다.

두 번째 줄에는 첫 번째 종류 컵케이크의 재료비 a와 이익 A가 주어진다.

세 번째 줄에는 두 번째 종류 컵케이크의 재료비 b와 이익 B가 주어진다.

Ugnė가 컵케이크를 팔아 얻을 수 있는 최대 이익을 정수 하나로 출력한다. 재료를 사려고 따로 빼 두었지만 쓰지 않은 돈은 최종 답에 포함되지 않는다.

정답은 $2\,000\,000\,000$ 을 넘지 않는다.