#H1003. 移动

移动

题目背景

小明又去工地搬砖了。

题目描述

工地上一共有 nn 堆砖头,第 ii 堆砖头有 aia_i 个。小明每次可以从一堆砖头中拿出一块或两块并放到任意的砖头堆中。小明希望最终第 ii 堆会有 bib_i 块砖头,请你帮小明求出他最少需要搬运几次,或判断无解。

我们认为,搬砖过程中,可以出现某一堆砖包含负数块的情况。

输入格式

第一行一个整数 nn,表示砖头堆的数量。

第二行 nn 个非负整数 a1ana_1\sim a_n,表示初始每一堆的砖头数。

第三行 nn 个非负整数 b1bnb_1\sim b_n,表示每一堆的目标砖头数。

输出格式

一行一个整数,表示最少的搬运次数。如果无解,则输出 1-1

3
1 3 5
5 3 1
2

样例1解释

两次从第三堆取两块砖放到第一堆即可。

4
1 3 5 7
4 4 4 4
3

样例2解释

从第三堆取一块砖放到第二堆,从第四堆取一块砖放到第一堆,再从第四堆取两块砖放到第一堆,共三次操作。

数据范围

对于 100%100\% 的数据,满足 1n1061\le n\le 10^60ai,bi1090\le a_i,b_i\le 10^9

测试点编号 nn\le ai,bia_i,b_i\le 特殊性质
11 22 1010
22 1010 100100 保证每一对 ai,bia_i,b_i 奇偶性相同
33
454\sim 5 10001000 保证每一对 ai,bia_i,b_i 奇偶性相同
676\sim 7
88 10610^6 10910^9 保证每一对 ai,bia_i,b_i 奇偶性相同
9109\sim 10

大样例

大样例下载