Вернувшись из очередного похода, Оргрим Думхаммер обнаружил, что его поселение было полностью разрушено отрядами людей. Теперь ему придется заново отстраивать город, восстанавливая его из руин.
Прежде всего, вождю Орды предстоит решить проблему с продовольствием – построить достаточное количество ферм (pig farm), чтобы его воины и рабочие не умерли от голода. Естественно, для этой работы Оргрим привлек всех своих пеонов (батраков).
На постройку одной фермы требуется G_f единиц золота, при этом она обеспечивает продовольствием P_f орков. Однако каждая ферма должна строиться в непосредственной близости от какого-либо зала вождей (great hall). Поэтому необходимо будет создать предварительно некоторое количество залов вождей. В окрестности одного зала вождей может быть построено не более F ферм. При этом возведение каждого зала вождей требует G_h единиц золота, но зато может обеспечить продовольствием P_h орков.
Помогите Оргриму написать продовольственную программу, которая определит сколько нужно построить залов вождей и ферм для обеспечения продовольствием N орков, затратив на строительство минимальное количество единиц золота.
Данные находятся в единственной строке входного файла и представляют собой шесть целых чисел N, F, G_h, P_h, G_f, P_f (0 ≤ N ≤ 10^6, 1 ≤ F ≤ 100, 1 ≤ G_h,G_f ≤ 2000, 0 ≤ P_h,P_f ≤ 1000, P_f≠0).
В единственную строку выходного файла выведите единственное число – искомое минимальное количество золота.