Smithing Skill
Contest: Educational Codeforces Round 167 (Rated for Div. 2)
Difficulty rating: 1900
Tags: brute force, data structures, dp, greedy, math, sortings, two pointers

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?

Input format:
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 format:
Print one integer — the maximum total experience points you can gain by repeatedly forging and melting weapons.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first example, you can do the following:

1. craft one weapon of the $$$1$$$-st class from the $$$1$$$-st type of metal, spending $$$9$$$ ingots;
2. melt that weapon, returning $$$8$$$ ingots of the $$$1$$$-st metal type;
3. again, craft and melt one weapon of the $$$1$$$-st class from the $$$1$$$-st metal type;
4. craft and melt one weapon of the $$$3$$$-rd class from the $$$1$$$-st metal type;
5. craft and melt one weapon of the $$$3$$$-rd class from the $$$3$$$-rd metal type;
6. craft and melt one weapon of the $$$4$$$-th class from the $$$1$$$-st metal type;
7. craft and melt one weapon of the $$$5$$$-th class from the $$$3$$$-rd metal type;

Example input:
5 3
9 6 7 5 5
8 4 5 1 2
10 4 7

Example output:
12

Example input:
3 4
10 20 20
0 0 0
9 10 19 20

Example output:
8

Editorial:
It's quite obvious that we should melt every weapon we forge, and we can do it as soon as we forge it. So, let's do these actions in pairs: forge a weapon, then instantly melt it.
Since you can't use two types of metal while forging one weapon, we can solve our task independently for each metal type. Suppose you have $$$x$$$ ingots of the chosen metal.
You can act greedily: you can forge only weapons of classes with $$$a_i \le x$$$, but among them, it's optimal to chose one that makes us lose the minimum number of ingots by forging it and melting it; so, we need to minimize the value of $$$a_i - b_i$$$. However, this greedy solution is too slow when implemented naively.
Let's define $$$A = \max{a_i}$$$ and look at two cases: $$$x \le A$$$ or $$$x > A$$$. If $$$x \le A$$$, let's just precalculate answers $$$\mathrm{ans}[x]$$$ for all $$$x$$$ from $$$0$$$ to $$$A$$$. To do so, let's precalculate another value $$$\mathrm{best}[x]$$$ as "the minimum $$$a_i - b_i$$$ among all classes $$$i$$$ where $$$a_i \le x$$$". In other words, $$$\mathrm{best}[x]$$$ will be equal to the minimum amount of ingots you'll lose if you have $$$x$$$ ingots, and you need to forge-melt one weapon.
We can precalculate $$$\mathrm{best}[x]$$$ in two steps:
1. for each class $$$i$$$, we can set $$$\mathrm{best}[a_i] = \min{(\mathrm{best}[a_i], a_i - b_i)}$$$;
2. using approach similar to prefix minima or dynamic programming, we can also update $$$\mathrm{best}[x] = \min{(\mathrm{best}[x], \mathrm{best}[x - 1])}$$$ for all $$$x$$$ from $$$1$$$ to $$$A$$$.
In case $$$x > A$$$, we can forge-melt a weapon with minimum $$$a_i - b_i$$$ as many times as we can until $$$x \le A$$$. Once $$$x$$$ becomes less or equal to $$$A$$$, we can take the value $$$\mathrm{ans}[x]$$$ and finish processing that metal type.
Knowing that the minimum $$$a_i - b_i$$$ is just $$$\mathrm{best}[A]$$$, we can reformulate our first step as finding minimum $$$k$$$ such that $$$x - k \cdot \mathrm{best}[A] \le A$$$ or $$$k \ge \frac{x - A}{\mathrm{best}[A]}$$$. In other words, we'll make the first step exactly $$$k = \left\lceil \frac{x - A}{\mathrm{best}[A]} \right\rceil$$$ times. So we can calculate the final answer as $$$2k + \mathrm{ans}[x - k \cdot \mathrm{best}[A]]$$$.
As a result, we run precalculating in $$$O(n + A)$$$ time and process each metal type in $$$O(1)$$$ time. The total complexity is $$$O(n + m + A)$$$ time and space.