Weighted Median

Time Limit: 2000 ms Memory Limit: 65536 KiB

Problem Description

For n elements x1, x2, ..., xn with positive integer weights w1, w2, ..., wn. The weighted median is the element xk satisfying
 and  , S indicates 
Can you compute the weighted median in O(n) worst-case?
 

Input

There are several test cases. For each case, the first line contains one integer n(1 ≤  n ≤ 10^7) — the number of elements in the sequence. The following line contains n integer numbers xi (0 ≤ xi ≤ 10^9). The last line contains n integer numbers wi (0 < wi < 10^9).
 

Output

One line for each case, print a single integer number— the weighted median of the sequence.
 

Sample Input

7
10 35 5 10 15 5 20
10 35 5 10 15 5 20

Sample Output

20

Hint

The S which indicates the sum of all weights may be exceed a 32-bit integer. If S is 5,  equals 2.5.

Source

2014年山东省第五届ACM大学生程序设计竞赛