Hide

Problem D
Refrigerator Transport

A factory that constructs refrigerator will deliver a shipment of $n$ refrigerators to a store. The factory has two cars it can use:

  • Car A costs $p_ a$ Swedish kronor per trip, and can load $k_ a$ refrigerators per trip.

  • Car B costs $p_ b$ Swedish kronor per trip, and can load $k_ b$ refrigerators per trip.

When transporting the refrigerators, each of the cars can be used any number of times. Depending on how many trips each car performs, one would get a different total cost of transporting all the refrigerators. Your task is to write a program that takes this data and computes how many trips each car should take in order to minimize this cost.

Input

The first and only line of input contains five integers separated by spaces:

  • the cost per trip $p_ a$ ($500 \le p_ a \le 2\, 000$) of car A,

  • the capacity per trip $k_ a$ ($10 \le k_ a \le 50$) of car A,

  • the cost per trip $p_ b$ ($500 \le p_ b \le 2\, 000$) of car B,

  • the capacity per trip $k_ b$ ($10 \le k_ b \le 50$) of car B, and

  • the number of refrigerators to transport $n$ ($1 \le n \le 1\, 000$).

Output

Output a single line with three integers – the number of trips the first car should make, the number of trips the second car should make, and the total cost of transportation. For all given inputs, this answer is unique.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.

Group

Points

Constraints

$1$

$33$

Only car A should make any trips in the optimal solution.

$2$

$67$

No additional constraints

Sample Input 1 Sample Output 1
960 13 995 14 150
4 7 10805

Please log in to submit a solution to this problem

Log in