Food Program
Returning from another expedition, Orgrim Doomhammer found his settlement completely destroyed by human forces. Now, he must rebuild the city from its ruins.
The first priority for the Warchief is to solve the food supply issue by constructing enough farms (pig farm) to ensure his warriors and workers do not go hungry. Naturally, Orgrim has enlisted all his peons (laborers) for this task.
Constructing one farm requires G_f units of gold and it provides food for P_f orcs. However, each farm must be built near a great hall. Therefore, a certain number of great halls must be constructed first. Around each great hall, no more than F farms can be built. Additionally, constructing each great hall requires G_h units of gold, and it can provide food for P_h orcs.
Help Orgrim develop a food supply plan that determines the number of great halls and farms needed to feed N orcs, while minimizing the gold spent on construction.
Input
The input consists of a single line containing six integers: 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).
Output
Output a single number on one line—the minimum amount of gold required.