Fair Distribution

시간 제한1초메모리 제한1024 MB

요약

N개의 설계도를 두 아이에게 나누고, 지상층 G와 주거층 높이 R인 설계도는 G + kR (k >= 1)의 높이를 만들 수 있다. 두 아이의 건물 높이 합을 같게 만드는 분배가 있는지 판정한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 그리디, 수학, 배열
정답자: 아직 제출이 없습니다

문제

An entrepreneur has $N$ blueprints, each describing a type of building. Each blueprint specifies the building’s height through two integers $G$ and $R$ .

$G$ : Height of the ground floor. It can be zero, indicating that the building has no ground floor.

$R$ : Height of each residential floor. Each building has at least one residential floor.

The entrepreneur wants to distribute all of these blueprints among their two children Alice and Bob. Each child will build exactly one building from each blueprint allocated to them, choosing the number of residential floors for each building.

The entrepreneur wants to avoid showing favoritism towards either child, so they are looking for a fair distribution of the blueprints. They decided that a fair distribution is one in which it is possible to construct the buildings in such a way that the sum of the heights of the buildings constructed by each child is the same. Can you tell whether a fair distribution exists?

Consider the following example for $N = 3$ blueprints:

$G = 1$ and $R = 1$ (possible heights are $2, 3, 4, \dots$ );
$G = 0$ and $R = 3$ (no ground floor, possible heights are $3, 6, 9, \dots$ );
$G = 2$ and $R = 1$ (possible heights are $3, 4, 5, \dots$ ).

In this case a possible fair distribution is assigning the second blueprint to Alice and the rest to Bob. Even though Alice receives a single blueprint while Bob receives two, they may construct two residential floors on the first building type (height $3$ ), two residential floors on the second (height $6$ ), and one residential floor on the third (height $3$ ). In this way, the sum of the heights of the buildings constructed by each child would be $6$ .

입력

The first line contains an integer $N$ ( $1 ≤ N ≤ 2 \cdot 10^5$ ) indicating the number of blueprints.

Each of the next $N$ lines contains two integers $G$ ( $0 ≤ G ≤ 2 \cdot 10^5$ ) and $R$ ( $1 ≤ R ≤ 10^9$ ) denoting respectively the height of the ground floor and the height of each residential floor specified by the corresponding blueprint. The sum of the heights of the ground floors of all blueprints is at most $2 \cdot 10^5$ .

출력

Output a single line with the uppercase letter “Y” if there exists a fair distribution of the blueprints, and the uppercase letter “N” otherwise.

예제4

예제 1
입력
```
3
1 1
0 3
2 1
```
예상 출력
```
Y
```
예제 2
입력
```
3
3 2
2 1
3 2
```
예상 출력
```
Y
```
예제 3
입력
```
3
1 10
2 20
4 30
```
예상 출력
```
N
```
예제 4
입력
```
1
1 1
```
예상 출력
```
N
```