Smithing Skill
Description
You are playing a famous computer game (that just works) where you have various skills you can level up. Today, you focused on the "Smithing" skill. Your tactic is obvious: forging weapons from ingots and then melting them back to return the materials partially. For simplicity, every time you create an item, you get $1$ experience point, and every time you melt an item, you also get $1$ experience point.
There are $n$ classes of weapons you can forge and $m$ types of metal ingots.
You can create one weapon of the $i$-th class, spending $a_i$ ingots of metal of the same type. Melting a weapon of the $i$-th class (which you crafted earlier) returns you $b_i$ ingots of the type of metal it was made of.
You have $c_j$ metal ingots of the $j$-th type, and you know that you can craft a weapon of any class from any metal type. Each combination of a weapon class and a metal type can be used any number of times.
What is the maximum total amount of experience you can earn by crafting and melting weapons?
The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^6$) — the number of weapon classes and metal types.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$), where $a_i$ is the number of ingots you need to forge one weapon of the $i$-th class.
The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($0 \le b_i < a_i$), where $b_i$ is the number of ingots you return by melting one weapon of the $i$-th class you forged earlier.
The fourth line contains $m$ integers $c_1, c_2, \dots, c_m$ ($1 \le c_j \le 10^9$) — the number of ingots you have of the corresponding metal type.
Print one integer — the maximum total experience points you can gain by repeatedly forging and melting weapons.
Input
The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^6$) — the number of weapon classes and metal types.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$), where $a_i$ is the number of ingots you need to forge one weapon of the $i$-th class.
The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($0 \le b_i < a_i$), where $b_i$ is the number of ingots you return by melting one weapon of the $i$-th class you forged earlier.
The fourth line contains $m$ integers $c_1, c_2, \dots, c_m$ ($1 \le c_j \le 10^9$) — the number of ingots you have of the corresponding metal type.
Output
Print one integer — the maximum total experience points you can gain by repeatedly forging and melting weapons.
5 3
9 6 7 5 5
8 4 5 1 2
10 4 7
3 4
10 20 20
0 0 0
9 10 19 20
1 5
3
1
1000000000 1000000000 1000000000 1000000000 1000000000
12
8
4999999990
Note
In the first example, you can do the following:
- craft one weapon of the $1$-st class from the $1$-st type of metal, spending $9$ ingots;
- melt that weapon, returning $8$ ingots of the $1$-st metal type;
- again, craft and melt one weapon of the $1$-st class from the $1$-st metal type;
- craft and melt one weapon of the $3$-rd class from the $1$-st metal type;
- craft and melt one weapon of the $3$-rd class from the $3$-rd metal type;
- craft and melt one weapon of the $4$-th class from the $1$-st metal type;
- craft and melt one weapon of the $5$-th class from the $3$-rd metal type;