409108: GYM103438 N A-series

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

N. A-seriestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

There are $$$N+1$$$ different sizes of paper: $$$A0$$$, $$$A1$$$, $$$A2$$$, $$$\ldots$$$, $$$AN$$$, where each size is twice larger than the next one.

You have $$$a_0$$$ pieces of paper of size $$$A0$$$, $$$a_1$$$ of size $$$A1$$$, $$$\ldots$$$, $$$a_{N}$$$ pieces of size $$$AN$$$. You want to obtain at least $$$b_0$$$ pieces of size $$$A0$$$, $$$b_1$$$ of size $$$A1$$$, $$$\ldots$$$, $$$b_{N}$$$ pieces of size $$$AN$$$. At any point you can fold and cut a paper in half, obtaining two pieces of smaller size (e.g. $$$A4 \rightarrow A5 \times 2$$$). What is the minimum number of cuts needed to obtain the required pieces?

Input

The first line contains a single integer $$$N$$$ ($$$1 \le N \le 2\cdot 10^5$$$).

The second line contains $$$N+1$$$ integers $$$a_0, a_1, \ldots, a_N$$$ ($$$0 \le a_i \le 10^9$$$).

The third line contains $$$N+1$$$ integers $$$b_0, b_1, \ldots, b_N$$$ ($$$0 \le b_i \le 10^9$$$).

Output

Output a single integer — the minimum number of cuts needed to obtain the required pieces, or $$$-1$$$, if it's not possible to obtain them.

ExamplesInput
1
10 0
0 19
Output
10
Input
1
10 0
0 21
Output
-1
Input
3
2021 11 21 10
10 21 11 2021
Output
1758

加入题单

上一题 下一题 算法标签: