Dome Stadium

A baseball team is planning to build a domed stadium. The city is laid out as $N$ villages in a straight line along a single highway, and each village sits at a distinct integer coordinate on the x-axis. From a survey, the team already knows how many baseball fans live in each village.

The team wants to place the stadium in one of the villages so that the total travel distance from every fan to the stadium is as small as possible. A village that holds $f$ fans and sits at distance $d$ from the stadium contributes $f \times d$ to this total. In other words, if a village's coordinate is $x_i$ and the chosen stadium coordinate is $p$, the total distance is the sum of $f_i \times |x_i - p|$ over all villages.

For example, suppose there are 5 villages at coordinates $(1, 2, 5, 7, 8)$ with fan counts $(3, 2, 4, 3, 1)$. Building the stadium in the village at x-coordinate $5$ minimizes the total distance from all fans.

Write a program that finds the village coordinate that minimizes the total distance from every fan to the stadium. The stadium must be built in one of the villages, and every village lies on an integer x-coordinate.

The input is read from standard input. The first line contains an integer $T$, the number of test cases. Each test case is given on three lines.

• The first line contains an integer $N$ ($1 < N \le 100000$), the number of villages.
• The second line contains $N$ integers, the village coordinates on the x-axis in ascending order. Each coordinate is between $1$ and $100000000$.
• The third line contains $N$ positive integers, the number of fans in each village. Each count is between $1$ and $10000$.

Write to standard output. For each test case, print exactly one line containing a single integer: the coordinate of the village that minimizes the total distance from all fans to the stadium. If several villages achieve the same minimum, print the smallest such coordinate.