Prof. Pang’s Arbitrage

Professor Pang has only 1 Au in his pocket. In order to make money he is allowed to perform a number of transactions at two types of stores: a balloon store and a candy store. The balloon store has only \(n_b\) balloons available while the candy store has only \(n_c\) candies available. All transactions must be performed exactly in their stated batches (i.e. no fractional transactions are allowed).

At the balloon store the following operations are available:

• Spend 1 Au to buy exactly \(k_{ab}\) balloons. This consumes \(k_{ab}\) balloons from the store.
• Spend 1 candy to buy exactly \(k_{cb}\) balloons. This also consumes \(k_{cb}\) balloons from the store.

At the candy store the following operations are available:

• Spend 1 Au to buy exactly \(k_{ac}\) candies. This uses \(k_{ac}\) candies from the store.
• Spend 1 balloon to buy exactly \(k_{bc}\) candies. This uses \(k_{bc}\) candies from the store.

Prof. Pang can also sell items:

• Selling 1 balloon gets him \(k_{ba}\) Aus.
• Selling 1 candy gets him \(k_{ca}\) Aus.

He may perform these six types of transactions in any order (possibly interleaved) any number of times as long as the store supplies are not exceeded. Note that once an item is bought from a store the store’s supply decreases permanently even if Prof. Pang sells that item later.

In summary, the available transactions are:

• Operation A: Au \(\to\) balloon (buy \(k_{ab}\) balloons for 1 Au, using the balloon store).
• Operation B: Au \(\to\) candy (buy \(k_{ac}\) candies for 1 Au, using the candy store).
• Operation C: candy \(\to\) balloon (buy \(k_{cb}\) balloons for 1 candy, using the balloon store).
• Operation D: balloon \(\to\) candy (buy \(k_{bc}\) candies for 1 balloon, using the candy store).
• Operation E: sell balloon (each balloon gets \(k_{ba}\) Aus).
• Operation F: sell candy (each candy gets \(k_{ca}\) Aus).

There are two independent “paths” to convert Au into more Au:

1. The Balloon Path:
   Prof. Pang may start with 1 Au to buy balloons (Operation A). He then has a choice:
   • Direct conversion: Sell the balloons directly (Operation E), yielding a total of \(k_{ab}\times k_{ba}\) Aus per 1 Au spent.
   • Indirect conversion: First convert the balloons into candies (Operation D) and then sell the candies (Operation F), yielding \(k_{bc}\times k_{ca}\) Aus per 1 Au spent.
   The balloon store supply limits the total number of Operation A transactions to \(\lfloor\frac{n_b}{k_{ab}}\rfloor\), and the candy store supply limits the indirect conversion path to at most \(\lfloor\frac{n_c}{k_{bc}}\rfloor\) transactions.
2. The Candy Path:
   Alternatively, Prof. Pang may use his Au to buy candies (Operation B). Then he can:
   • Direct conversion: Sell the candies (Operation F), yielding \(k_{ac}\times k_{ca}\) Aus per 1 Au spent.
   • Indirect conversion: Convert candies into balloons (Operation C) and then sell the balloons (Operation E), yielding \(k_{ac}\times k_{cb}\times k_{ba}\) Aus per 1 Au spent.
   Here, the candy store limits Operation B to \(\lfloor\frac{n_c}{k_{ac}}\rfloor\) transactions, and the balloon store limits the indirect conversion path to at most \(\lfloor\frac{n_b}{k_{cb}}\rfloor\) transactions.

Your task is to help Prof. Pang determine the maximum number of Aus he can have after performing a sequence of these transactions optimally.

inputFormat

The input consists of a single line containing eight positive integers:

\(k_{ab}\) \(k_{cb}\) \(k_{ac}\) \(k_{bc}\) \(k_{ba}\) \(k_{ca}\) \(n_b\) \(n_c\)

These represent the parameters in the description above.

outputFormat

Output a single integer: the maximum number of Aus Prof. Pang can have if he performs the transactions optimally.

sample

2 3 2 2 2 3 10 10

468177408