Maximal Rabbit Jump Duration

There are N rabbits placed on a number line. The i-th rabbit is initially at position x_i with energy p_i. Additionally, there are M carrots placed on the number line; the i-th carrot is located at position y_i and has a mass of t_i kilograms.

Every second, the following events occur:

1. If at least one rabbit has energy equal to 0, the process stops immediately.
2. Otherwise, every rabbit jumps to the right by 1 unit and loses 1 unit of energy.

After the jump, if a rabbit lands on a position with one or more carrots, it may choose to eat an amount a (where \(0 \le a \le t\); here, \(t\) is the current mass of that carrot). Eating \(a\) kilograms of carrot increases the rabbit's energy by \(a\), while the carrot's mass decreases by \(a\).

Note that once a rabbit stops jumping (when its energy becomes 0), it will never jump again. Under an optimal strategy, determine the maximum number of seconds all rabbits can keep jumping.

The key observation is that each rabbit i must have a total energy (initial energy plus any energy gained from carrots when it lands on them) at least equal to the number of seconds T in order to jump T times. For each rabbit, the extra energy required is \(\max(0, T - p_i)\). However, each carrot at position \(y_j\) can only help rabbits that land on it; a rabbit starting at \(x_i\) reaches position \(y_j\) after \(y_j - x_i\) seconds. Thus, rabbit i can make use of the carrot only if \(y_j - T \le x_i \le y_j\).

This problem can be solved by performing a binary search on \(T\) (the number of seconds) and using a greedy strategy to allocate the limited carrot resource to the rabbits in order to meet their energy deficits.

inputFormat

The input consists of five lines:

• The first line contains two integers N and M, representing the number of rabbits and carrots respectively.
• The second line contains N integers: x₁, x₂, ..., x_N, where x_i is the initial position of the i-th rabbit.
• The third line contains N integers: p₁, p₂, ..., p_N, where p_i is the initial energy of the i-th rabbit.
• The fourth line contains M integers: y₁, y₂, ..., y_M, representing the positions of the carrots.
• The fifth line contains M integers: t₁, t₂, ..., t_M, where t_i is the mass (in kilograms) of the i-th carrot.

outputFormat

Output a single integer representing the maximum number of seconds that all rabbits can jump under an optimal strategy.

sample

3 2
1 2 3
3 1 2
4 5
2 1

4