У Василия есть машина и он хочет добраться от дома до почты. Расстояние, которое ему нужно преодолеть, равно d километрам.
Машина у Василия не новая — после того, как она проезжает k километров, она каждый раз ломается и её надо чинить t секунд. После починки машины Василий может снова ехать на ней (но после k километров она опять сломается и так далее). Изначально, можно считать, что машина только что из ремонта.
На проезд одного километра на машине Василий тратит a секунд, на похождение одного километра пешком — b секунд (a < b).
Перед вами стоит задача определить, за какое минимальное время Василий сможет добраться до почты, если в любой момент времени он может оставить машину и пойти пешком?
Выходные данные
Выведите минимальное время, по истечении которого Василий сможет добраться до почты.
Примечание
В первом примере Василию нужно проехать первые 2 километра на машине (за 2 секунды), а затем дойти оставшиеся 3 километра пешком (за 12 секунд). Таким образом, ответ равен 14-ти секундам.
Во втором примере Василию выгодно проехать первые 2 километра на машине (за 2 секунды), затем починить машину (за 5 секунд) и проехать еще 2 километра на машине (за 2 секунды). После этого ему нужно дойти оставшийся 1 километр пешком (за 4 секунды). Таким образом, ответ равен 13-ти секундам.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2 1 4 10
|
14
|
|
2
|
5 2 1 4 5
|
13
|