Weights and Scales

Bajtek received a set of $n$ black weights, $n$ gray weights, and $n$ very light balance scales. Each scale has two pans.

He built one nested tower. He put the first scale on the floor. On one pan of it he placed the first black weight, and on the other pan he placed the second scale. On one pan of the second scale he placed the second black weight, and on its other pan the third scale, and so on. On the last, $n$-th scale he placed the $n$-th black weight on one pan and left the other pan empty.

Now for the puzzle. On the single empty pan you may place any one gray weight. Whenever some scale is in balance, meaning its two pans hold the same total mass, you may replace that whole scale together with everything resting on it by a single gray weight of the same total mass, as long as a gray weight of exactly that mass is still available. The scales themselves have negligible mass.

Bajtek wants the finished tower to hold as few weights as possible, so that he can easily mail it to his friend Bitoasia. Find the smallest number of weights that can remain in the tower.

The first line contains one integer $n$ ($1 \le n \le 10^6$), the number of scales.

The second line contains $n$ integers $c_i$ ($1 \le c_i \le 10^{18}$) separated by single spaces: the masses of the black weights, where $c_1$ sits on the scale on the floor and $c_{i+1}$ sits on a pan of the scale that carries $c_i$.

The third line contains $n$ integers $s_j$ ($1 \le s_j \le 10^{18}$) separated by single spaces: the masses of the gray weights.

Print one integer: the minimum number of weights that can remain in the tower.