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.


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$.


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
2 1
2 1
2 1
Sample Input 2 Sample Output 2
5 0
5 0
0 5
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 4.0medium
Statistics Show
Languages English, Svenska
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in