На Киберленд напало чудовище!
Отважный мастер Янь собирается сражаться с чудовищем. У Яня и чудовища есть по три атрибута: очки здоровья (HP), сила атаки (ATK) и сила защиты (DEF).
За каждую секунду сражения HP чудовища уменьшается на max(0, ATKY - DEFM), а HP Яня уменьшается на max(0, ATKM - DEFY), где индекс Y обозначает мастера Яня, а индекс M обозначает чудовище. Уменьшение происходит одновременно. Как только у чудовища HP ≤ 0, а у мастера Яня в то же время HP > 0, мастер Янь побеждает.
Мастер Янь может купить увеличение атрибутов в киберлендском магазине волшебства: h биткоинов за очко HP, a биткоинов за очко ATK, и d биткоинов за очко DEF.
Теперь Мастер Янь хочет знать, какое наименьшее количество биткоинов ему надо потратить, чтобы победить.
Выходные данные
В единственной строке вывода выведите единственное целое число, обозначающее минимальное количество биткоинов, которые мастер Янь должен потратить для победы.
Примечание
В первом примере цены на ATK и DEF очень высокие. Мастер Янь может купить 99 HP, тогда он сможет победить чудовище и остаться с 1 HP в запасе.
Во втором примере мастер Янь достаточно силен, чтобы сразу победить чудовище, так что покупать ничего не надо.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 2 1
1 100 1
1 100 100
|
99
|
|
2
|
100 100 100
1 1 1
1 1 1
|
0
|