Maximizing Experience Before Falling

You are given n types of attacks. The i-th attack gives you \(a_i\) experience points and decreases your health by \(b_i\) points.

You will be attacked sequentially k times. The type of the \(i\)-th attack is given by \(c_i\). Your initial health is \(m\).

To help you survive longer and gain more experience, you are allowed to choose one attack type among the \(n\) types, and the first occurrence of that attack type will be blocked (i.e. its effects are canceled, so you neither lose health nor gain experience).

Your task is to determine the maximum total experience you can obtain before your health drops to 0 or below. Note: The simulation stops immediately when an attack would cause your health to become 0 or less; the attack that causes your health to drop is not applied.

Input Format (in one test case):

• The first line contains three integers \(n\), \(m\), and \(k\) — the number of attack types, the initial health, and the number of attacks respectively.
• The second line contains \(n\) integers: \(a_1, a_2, \dots, a_n\), where \(a_i\) is the experience gained from the \(i\)-th type of attack.
• The third line contains \(n\) integers: \(b_1, b_2, \dots, b_n\), where \(b_i\) is the health lost when hit by the \(i\)-th type of attack.
• The fourth line contains \(k\) integers: \(c_1, c_2, \dots, c_k\) — the sequence of attacks (each \(c_i\) is between 1 and \(n\)).

Output:

Output a single integer representing the maximum total experience you can obtain by choosing an optimal attack type to block its first occurrence.

inputFormat

The input consists of four lines:

1. The first line contains three space-separated integers: n m k.
2. The second line contains n space-separated integers: a_1 a_2 ... a_n.
3. The third line contains n space-separated integers: b_1 b_2 ... b_n.
4. The fourth line contains k space-separated integers: c_1 c_2 ... c_k.

outputFormat

Output a single integer: the maximum experience obtainable.

sample

2 10 4
3 5
4 7
1 2 1 2

6