Problem H

For n elements x₁, x₂, ..., x_n with positive integer weights w₁, w₂, ..., w_n. The weighted median is the element x_k satisfying

and , S indicates .

Can you compute the weighted median in O(n) worst-case?

There are several test cases. For each case, the first line contains one integer n (1 ≤ n ≤ 10⁷) — the number of elements in the sequence. The following line contains n integer numbers x_i (0 ≤ x_i ≤ 10⁹). The last line contains n integer numbers w_i (0 < w_i < 10⁹).

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

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

20

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

计算机学院大学生程序设计竞赛（2014’12）