Groups of Bots
Description
You are given $N$ groups of robots, with the $i$th group having the coordinate $X_i$ on a number line. Also, the number of robots in the $i$th group is $A_i$. Not all groups of robots have a distinct coordinate $X_i$. If two groups of robots share the same $X_i$, they are combined into one larger group. Among all points on the number line with integer coordinate $Y$ such that $Y$ is different from all $X_i$, the following quantity has a minimum value:
The absolute difference between the sum of the distances from $Y$ to the robots left of $Y$ and the sum of the distances from $Y$ to the robots right of $Y$.
Find this minimum value.
Line 1: One integer, $N$.
Line 2…$N+1$: Line $i+1$ contains two integers, $X_i$ and $A_i$, separated by a space.
Line 1: One integer, representing the minimum possible value of the quantity:
The absolute difference between the sum of the distances from $Y$ to the robots left of $Y$ and the sum of the distances from $Y$ to the robots right of $Y$.
Input
Line 1: One integer, $N$.
Line 2…$N+1$: Line $i+1$ contains two integers, $X_i$ and $A_i$, separated by a space.
Output
Line 1: One integer, representing the minimum possible value of the quantity:
The absolute difference between the sum of the distances from $Y$ to the robots left of $Y$ and the sum of the distances from $Y$ to the robots right of $Y$.
3
1 5
6 4
9 3
5
7 6
5 8
7 2
10 7
8 7
4
42
Note
$1≤N≤10^5.$
$1≤X_i≤10^9.$
$1≤A_i≤10^4.$
If we choose $Y=5$, then only the input $1 5$ is to the left of $Y$, so "the sum of the distances from $Y$ to the robots left of $Y$" evaluates to $5⋅Y-1=20$. Similarly, "the sum of the distances from $Y$ to the robots right of $Y$" evaluates to $4⋅6-Y+3⋅9-Y=16$. The difference between $20$ and $16$ is $4$, so that is the output.