Дракон пил чай на балконе и любовался необычайно красивым закатом. В лучах заходящего солнца ещё можно было различить две удаляющиеся фигуры. Дракону было немного грустно: Принцесса, конечно, обещала как-нибудь заглянуть в гости, но зачем ей теперь возвращаться в Долину Замков?..

Он решил, что завтра попробует приготовить печенье, рецепт которого рассказала ему Принцесса. А для этого нужно посчитать, достаточно ли у него ингредиентов. Конечно, у него есть в запасе и имбирь, и корица, и гвоздика, и кардамон... Но для печенья их нужно больше, чем для заваривания чая.

Дракон пересчитал свои запасы, и теперь для каждого ингредиента знает, сколько единиц этого ингредиента имеется в наличии.

В рецепте указано, сколько единиц того или иного ингредиента требуется для изготовления одного печенья. Конечно, Дракон хочет изготовить целое количество печений.

Проведя вычисления, Дракон понял, что какие-то ингредиенты у него останутся, в то время как другие будут полностью израсходованы. Он подумал, что можно докупить такое количество ингредиентов, чтобы израсходовать все ингредиенты полностью.

Теперь он интересуется, сколько минимально ему понадобится на это денег. Стоимость единицы каждого ингредиента ему известна. Ваша задача — определить минимальную сумму, которую придётся потратить Дракону.