Problem Description

There are $N$ pairwise non-overlapping circles centered on the $x$ axis, but their circumferences may touch. How many regions do these circles divide the plane into?

Input Format

The first line contains an integer $N$, the number of circles.

Each of the next $N$ lines contains two integers $x_i$ and $r_i$, where $x_i$ is the $x$ coordinate of the center of the $i$-th circle, and $r_i$ is its radius.

All circles in the input are guaranteed to be unique.

Output Format

Output the number of regions into which these circles divide the plane.

2
1 3
5 1 

3

3
2 2
1 1
3 1 

5

4
7 5
-9 11
11 9
0 20 

6

Hint

Sample Explanation

Explanation for Sample 3

This sample corresponds to the figure below:

Constraints

• For $40\%$ of the testdata, $1 \le N \le 5\times 10^3$.
• For $100\%$ of the testdata, $1 \le N \le 3\times 10^5$, $-10^9 \leq x_i \leq 10^9$, $1 \leq r_i \leq 10^9$.

Notes

Translated from COCI2013-2014 CONTEST #6 T4 KRUŽNICE.

Translated by ChatGPT 5