Coin Exchange

Time limit2sMemory limit128 MB

Summary

Find the minimum number of fixed-rate gold/silver/bronze coin exchanges needed to reach required minimum amounts of each coin, or report impossibility.

Level: Medium6 of 10
Topics: Greedy, Math, Implementation
Solved: No attempts yet

Problem

Sejun currently has G1 gold coins, S1 silver coins, and B1 bronze coins. To buy a new laptop, he needs at least G2 gold coins, at least S2 silver coins, and at least B2 bronze coins.

At the bank, each exchange must be one of the following four types.

Exchange 1 gold coin for 9 silver coins.
Exchange 11 silver coins for 1 gold coin.
Exchange 1 silver coin for 9 bronze coins.
Exchange 11 bronze coins for 1 silver coin.

Find the minimum number of exchanges needed so that, after all exchanges, he has at least the required number of each coin.

Input

The first line contains the current numbers of coins, G1 S1 B1.

The second line contains the required numbers of coins, G2 S2 B2.

Every value is an integer between 0 and 1,000,000, inclusive.

Output

Print the minimum number of exchanges needed. If it is impossible to obtain the required numbers of coins, print -1.

Examples4

Example 1
Input
```
1 100 12
5 53 33
```
Expected output
```
7
```
Example 2
Input
```
1 0 0
0 0 81
```
Expected output
```
10
```
Example 3
Input
```
1 100 12
5 63 33
```
Expected output
```
-1
```
Example 4
Input
```
5 10 12
3 7 9
```
Expected output
```
0
```