407794: GYM102894 B Santa Claus Is Coming To Town

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Santa Claus Is Coming To Towntime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Despite the global pandemic, Santa Claus decided to give gifts to children for the New Year. It turned out that gifts should be given to $$$n$$$ boys and $$$m$$$ girls. He creates gifts with spells and a magic wand; moreover, it turned out that he spends different amounts of time on gifts for boys and gifts for girls — $$$x$$$ minutes and $$$y$$$ minutes on one gift, respectively.

In addition, there are gifts that Santa Claus considers universal — suitable for both girls and boys — it also takes him a certain amount of time to prepare them, and it is $$$z$$$ minutes.

But, unfortunately, it turned out that his magic sleigh can only hold $$$k$$$ gifts that are suitable for both boys and girls at the same time. Knowing this, help Santa Claus find out the minimum amount of time he will need to spend on preparing gifts.

Input

The first line contains an integer $$$n$$$ — the number of boys.

The second line contains an integer $$$m$$$ — the number of girls.

The third line contains an integer $$$x$$$ — the amount of time it takes to create a gift for boys.

The fourth line contains an integer $$$y$$$ — the amount of time it takes to create a gift for girls.

The fifth line contains an integer $$$z$$$ — the amount of time it takes to create a gift suitable for both boys and girls.

The sixth line contains an integer $$$k$$$ — the largest number of 'universal' gifts that Santa Claus can take with him.

The numbers do not exceed $$$10^9$$$.

Output

Output a single number — the minimum amount of time that Santa Claus needs to prepare the gifts for every child.

Scoring

PointsLimitsDependenciesGrading policy
117$$$k = 0$$$-each test
224$$$m = 0$$$-each test
334$$$n, m, k, x, y, z \le 100$$$-each test
410$$$n, m, k, x, y, z \le 10^5$$$-each test
515$$$n, m, k, x, y, z \le 10^9$$$-each test

ExamplesInput
9
17
4
3
2
10
Output
68
Input
10
10
5
7
6
500
Output
110
Note

In the first example, it is optimal to replace all gifts for boys with universal ones, and also to give a universal gift to one girl. Total $$$ 9 \ cdot 2 + 1 \ cdot 2 + 16 \ cdot 3 = 68 $$$ minutes.

In the second example, it is optimal to replace only gifts for girls, because Santa Claus can prepare gifts for boys quickly.

加入题单

上一题 下一题 算法标签: