A Romantic Dinner Outing

Brian the Computer Science Nerd is going on a date with his girlfriend, Anatevka! His romantic location of choice is a Chinese restaurant.

At this restaurant, N (1 ≤ N ≤ 15) different dishes are available, and Brian would like to order each one exactly once. The waiter will come to his table to take orders N times - the i-th time he comes will be W_i (1 ≤ W₁ < W₂ < … < W_N ≤ 10⁹) minutes after the start of the meal. He has quite a poor memory, so each time he comes by, Brian will have a chance to order exactly one new dish.

Dish i takes T_i (1 ≤ T_i ≤ 10⁹) minutes to prepare, which means that it will generally come exactly that many minutes after being ordered, delivered by a different waiter who will not take orders. However, meals are guaranteed to arrive in the same order in which they were ordered - this means that, if meal i was ordered before meal j, but meal j is ready before meal i, then meal j will instead arrive at the same time as meal i.

Now, Brian considers time spent waiting for the first meal after the start of the dinner, as well as for each subsequent meal after the previous one, to be idle time. Of course, these are the worst parts of the date, as they require actually engaging in conversation rather than consuming sustenance. In order to impress Anatevka with his optimal ordering skills, he'd like to minimize the length of the largest continuous stretch of idle time throughout the dinner.

Input

Line 1: 1 integer, N
Line 2: N integers, W_1..N
Line 3: N integers, T_1..N

Output

1 integer, the minimal length possible for the longest stretch of idle time throughout the meal, in minutes

Sample Input

3
1 5 6
4 2 3

Sample Output

4

Explanation of Sample

Brian's optimal strategy is to order dish 3, then 2, then 1. These dishes will then arrive 4, 7, and 10 minutes into the dinner, respectively. The longest stretch of idle time is then 4 minutes long.

As a further example, if Brian were to order dish 3, then 1, then 2, the last 2 dishes would both arrive 9 minutes into the dinner, with dish 2 being held up by dish 1.

All Submissions
Best Solutions

Point Value: 20
Time Limit: 2.00s
Memory Limit: 64M
Added: Jul 08, 2014
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, TEXT, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)