Task

Matsaki, leader of the 16^th movement, wants to denounce Michael, leader of the 17^th movement. Luckily, Squircle Academy is planning to have an afternoon consisting of a number of math presentations given by students, and Matsaki wants to give a speech during that time.

Students have proposed several presentations. Each student told about the time the presentation will be told: the i^th student wants to start his presentation at start[i] and finish it by finish[i]. There will be plenty time for the presentations, since the presentations can be scheduled at any time starting from 0 to end.

Each presentation has its priority. The presentations are stored in the array, with the first presentation having the highest priority, the second having the second highest priority, and so on. Starting with the presentation with highest priority, Squircle Academy will schedule a presentation if it doesn't interrupt a presentation that is already scheduled; otherwise the presentation will be rejected. (Two presentations interrupt each other if their intersection is a segment [a, b], where a ≠ b).

Matsaki wants as much time as possible in his presentation to denounce Michael, but his presentation will have the lowest priority and so will be considered last. What is the maximum length of the presentation Matsaki can give?

Input/Output

[input] integer array start

The starting times of the presentations, ordered by priority.

1 ≤ start.length ≤ 1000,

0 ≤ start[i] ≤ 10^7

[input] integer array finish

The ending times of the presentations.

finish.length = start.length

start[i] ≤ finish[i] ≤ 10^7

[input] integer end

The latest time that a presentation can end (or the end of the day).

7 ≤ end ≤ 10^7.

[output] an integer

The length of the optimal interval for the presentation.

Example

For start = [1, 5, 2], finish = [2, 9, 6] and end = 10,

the output should be 3.

- the first presentation should start at 1 and finish at 2. 
  Since no presentation has been scheduled so far, this time 
  is vacant, so the presentation is scheduled;

- the second presentation should start at 5 and finish at 9. 
  Since it doesn't interrupt the only scheduled presentation 
  (which is scheduled for the period [1, 2]), this presentation
  is scheduled too;

- the third presentation should start at 2 and finish at 6.
  This presentation doesn't interrupt the first first one,
  which will be told from 1 to 2 (they only intersect at the 
  endpoints), but it does interrupt the second presentation 
  scheduled for the period [5, 9] (their intersection is the 
  time interval [5, 6]). 

  So, the third presentation is rejected.

- now, there are two time intervals available for Matsaki: 
  from 2 to 5 (between the two scheduled presentations) and 
  from 9 to 10 (after the second one). 
  
  Thus, the longest period is from 2 to 5, which is 3.

Note that it doesn't matter that Matsaki's presentation and the third one intersect, since that presentation was rejected.