eolymp
bolt
Try our new interface for solving problems
Problems

Food program (RU)

Food program (RU)

Time limit 1 second
Memory limit 64 MiB

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

Прежде всего, вождю Орды предстоит решить проблему с продовольствием – построить достаточное количество ферм (pig farm), чтобы его воины и рабочие не умерли от голода. Естественно, для этой работы Оргрим привлек всех своих пеонов (батраков).

На постройку одной фермы требуется G_f единиц золота, при этом она обеспечивает продовольствием P_f орков. Однако каждая ферма должна строиться в непосредственной близости от какого-либо зала вождей (great hall). Поэтому необходимо будет создать предварительно некоторое количество залов вождей. В окрестности одного зала вождей может быть построено не более F ферм. При этом возведение каждого зала вождей требует G_h единиц золота, но зато может обеспечить продовольствием P_h орков.

Помогите Оргриму написать продовольственную программу, которая определит сколько нужно построить залов вождей и ферм для обеспечения продовольствием N орков, затратив на строительство минимальное количество единиц золота.

Input data

Данные находятся в единственной строке входного файла и представляют собой шесть целых чисел N, F, G_h, P_h, G_f, P_f (0N10^6, 1F100, 1G_h,G_f2000, 0P_h,P_f1000, P_f0).

Output data

В единственную строку выходного файла выведите единственное число – искомое минимальное количество золота.

Examples

Input example #1
9 5 1200 1 500 4
Output example #1
2200
Author vetal_n