Problem G
Wimbledon
A tennis match involves three people: two players and an umpire. Each of these has to come from a different country. There are $N$ countries, and the $i$th country has $a_ i$ tennis players and $b_ i$ umpires. (Nobody can be both a player and an umpire.) How many different tennis matches are possible? Two tennis matches are different if the sets of involved people are different.
Input
The first line contains an integer $N$, where $3 \leq N \leq 10^5$. The following $N$ lines each contain two integers $a_ i$ and $b_ i$ with $0 \leq a_ i, b_ i \leq 10^6$. You can assume $\sum _{i=1}^ N a_ i \leq 10^6$ and $\sum _{i=1}^ N b_ i \leq 10^6$.
Output
A single integer, the number of possible different tennis matches.
Explanation of Sample 1
Assume the players from the first country are called $A_1$ and $A_2$, the players from the second country are called $B_1$ and $B_2$, and the umpire from the third country is called $C$. Then there are $4$ matches where $C$ is the umpire: $\{ A_1, B_1, C\} $, $\{ A_1, B_2, C\} $, $\{ A_2, B_1, C\} $, and $\{ A_2, B_2, C\} $. Similarly, there are $8$ matches with the other umpires. In total, there are $12$ possible different matches.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 2 1 2 1 2 1 |
12 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 5 0 5 0 0 5 |
125 |
