Два станка

면접 대비

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

요약

두 기계가 각각 a분, b분의 준비 시간 뒤 분당 x개, y개를 생산하며 준비는 동시에 할 수 없을 때, k분 동안 만들 수 있는 최대 부품 수를 구한다.

난이도: 보통10점 중 4점
유형: 그리디, 수학, 구현, 완전 탐색
정답자: 아직 제출이 없습니다

문제

На производстве имеется два станка. Необходимо изотовить как можно больше деталей за сегодняшнюю смену, продложительность которой $k$ минут.

Станки находятся в законсервированном состоянии. Для того, чтобы ввести в строй первый станок, требуется $a$ минут, после чего он будет производить $x$ деталей в минуту. Для того, чтобы ввести в строй второй станок, требуется $b$ минут, после чего он будет производить $y$ деталей в минуту.

Для введения в строй станка требуется присутствие инженера, поэтому нельзя вводить в строй два станка одновременно. При этом введение станка в строй и изготовление деталей на другом станке, а также одновременное изготовление деталей на двух станках разрешается.

Требуется выяснить, какое максимальное количество деталей удастся изготовить за $k$ минут.

입력

В первой строке ввода дано единственное целое неотрицательное число $k$ --- количество минут в смене ( $0 \le k \le 10^9$ ).

Во второй строке ввода даны целые неотрицательные числа $a$ и $x$ --- время введения первого станка в строй и количество деталей, которое он изготавливает за одну минуту ( $0 \le a, x \le 10^9$ ).

В третьей строке ввода даны целые неотрицательные числа $b$ и $y$ --- время введения второго станка в строй и количество деталей, которое он изготавливает за одну минуту ( $0 \le b, y \le 10^9$ ).

출력

Выведите единственное число --- максимальное количество деталей, которое удастся изготовить за смену.

Обратите внимание, что ответ в этой задаче может быть довольно большим и не помещаться в 32-битные типы данных. Рекомендуется использовать 64-битный тип данных, например <<\mbox{long long}>> в C++ или <<int64>> в Паскале.

힌트

В примере выгодно сначала ввести в строй второй станок и за оставшиеся $15$ минут изготовить $45$ деталей, а затем ввести в строй первый и за оставшиеся $5$ минут изготовить на нём еще $20$ деталей.

Если сначала ввести в строй первый станок и изготовить на нем в оставшиеся $10$ минут $40$ деталей, то после введения в строй второго на нем удастся изготовить лишь $15$ деталей, суммарно $55$ , что меньше, чем $65$ .

예제1

예제 1
입력
```
20
10 4
5 3
```
예상 출력
```
65
```