has been training hard for programming contests! One day, he decides to study linear programming, which invariably gets him to learn about the simplex algorithm.
Unrelated to the simplex algorithm, ~C~ cacti and ~M~ matroids, then his joy is ~C U_c + M U_m~.has discovered that there are two things which spark joy in his life - cacti and matroids. If has
~C + M~ cannot be too large. Fortunately, is a resourceful individual and will be able to obtain arbitrarily many cacti and matroids subject to this constraint.is a busy person though, so
wishes to know the maximum joy that can be sparked.
~K, U_c, U_m \le 100~
In tests worth 5 marks, ~K = 1~.
In tests worth another 5 marks, ~U_c~ and ~U_m~ are both equal to ~1~.
The first line contains a single positive integer, ~U_c~, the amount of joy a single cactus sparks.
The second line contains a single positive integer, ~U_m~, the amount of joy a single matroid sparks.
The third line contains a single positive integer, ~K~. The total number of cacti and matroids that can own may not exceed ~K~.
Output, on a single line, the maximum amount of joy that can be sparked.
Sample Input 1
10 10 1
Sample Output 1
Sample Input 2
1 1 10
Sample Output 2