Temperature Adjustment

Interview

Time limit1sMemory limit1024 MB

Summary

Find the fewest presses so every beaker reaches its target when each press shifts beaker i by plus or minus X_i, or print -1 if no press count works.

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

Problem

A school lab has $N$ beakers numbered from $1$ to $N$ . The initial temperature of beaker $i$ is $A_i$ degrees Celsius.

Gihyeon must set every beaker to a target temperature. Beaker $i$ must reach $B_i$ degrees Celsius. Tired of adjusting each beaker by hand, Gihyeon built a temperature control device.

The device has one button. Each press changes the temperature of every beaker $i$ ( $1 \le i \le N$ ) by $X_i$ degrees, either up or down. Gihyeon chooses the direction for each beaker separately, but a beaker's temperature cannot stay the same. Each $X_i$ is fixed for its beaker and never changes.

Each press takes time, so Gihyeon wants to reach all target temperatures with the fewest presses. Given $N$ , the initial temperatures, the target temperatures, and the change values, find the minimum number of presses needed. Also determine when the device cannot bring every beaker to its target.

Input

The first line contains $N$ ( $1 \le N \le 100000$ ).

The second line contains $A_1, A_2, \cdots, A_N$ separated by spaces ( $0 \le A_i \le 10^9$ ).

The third line contains $B_1, B_2, \cdots, B_N$ separated by spaces ( $0 \le B_i \le 10^9$ ).

The fourth line contains $X_1, X_2, \cdots, X_N$ separated by spaces ( $1 \le X_i \le 10^9$ ).

Output

Print the minimum number of button presses needed to set every beaker to its target temperature.

If the device cannot reach the targets, print -1.

Examples2

Example 1
Input
```
3
1 3 5
5 9 5
2 3 4
```
Expected output
```
2
```
Example 2
Input
```
2
1 3
4 5
2 1
```
Expected output
```
-1
```