E - 待ち合わせ 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は N 人の友人と待ち合わせの計画を立てています。高橋君は司令塔として友人たちに移動の指示を出す役割であり、高橋君自身は移動せず、集合地点にいる必要もありません。

N 人の友人は数直線上にいます。友人 i（1 \leq i \leq N）は最初、座標 X_i にいます。どの 2 人の友人も、初期座標は互いに異なります。

各友人はちょうど T 回の移動を順に行います。友人 i の各回の移動では、現在の座標に +P_i または -P_i のいずれかを加えます。すなわち、移動前の座標が c であるとき、移動後の座標は c + P_i または c - P_i のどちらかになります。移動しない（変位 0）という選択はできません。

高橋君は、各友人の各回の移動について、+P_i と -P_i のどちらに移動するかを自由に指示することができます。各友人への指示は互いに独立であり、ある友人への指示が他の友人の移動に影響することはありません。

高橋君は、すべての友人がそれぞれちょうど T 回の移動を終えた後に、全員が同一の座標にいるように指示を出したいと考えています。判定するのは最終的な座標のみであり、移動の途中で友人同士が同じ座標にいるかどうかは問いません。また、全員が集合する座標は事前に定められておらず、どの座標でもかまいません。

このような移動方向の指示の仕方が存在するかどうかを判定してください。可能な場合は Yes を、不可能な場合は No を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq T \leq 10^{18}
  • -10^{18} \leq X_i \leq 10^{18}
  • 1 \leq P_i \leq 10^9
  • X_i はすべて異なる
  • 入力はすべて整数

入力

N T
X_1 P_1
X_2 P_2
\vdots
X_N P_N
  • 1 行目には、友人の人数を表す整数 N と、各友人が行う移動の回数を表す整数 T が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目（1 \leq i \leq N）には、友人 i の初期座標 X_i と、1 回の移動における移動距離を表す正の整数 P_i が、スペース区切りで与えられる。

出力

すべての友人がちょうど T 回移動した後に同じ座標に集合できる場合は Yes を、できない場合は No を 1 行で出力してください。

入力例 1

3 2
0 1
2 1
4 2

出力例 1

Yes

入力例 2

2 1
0 1
3 1

出力例 2

No

入力例 3

6 5
4 2
13 3
5 1
22 4
35 5
3 7

出力例 3

Yes

入力例 4

15 1000000000000
0 1
-6 3
20 5
-700 7
2200 11
-1604928 13
11123440 17
-1000000000 1
2000000000 2
-3000000000 3
4000000000 4
-500000000000000000 500000000
600000000000000000 600000000
-999999998000000000 1000000000
999999996000000000 1000000000

出力例 4

Yes

入力例 5

1 1000000000000000000
-1000000000000000000 1000000000

出力例 5

Yes

Score : 466 pts

Problem Statement

Takahashi is planning a meetup with N friends. Takahashi acts as the commander, giving movement instructions to his friends. Takahashi himself does not move and does not need to be at the meeting point.

The N friends are on a number line. Friend i (1 \leq i \leq N) is initially at coordinate X_i. No two friends share the same initial coordinate.

Each friend performs exactly T moves in sequence. In each move of friend i, either +P_i or -P_i is added to their current coordinate. That is, if the coordinate before the move is c, the coordinate after the move becomes either c + P_i or c - P_i. Choosing not to move (displacement 0) is not allowed.

Takahashi can freely instruct each friend, for each of their moves, whether to move by +P_i or -P_i. The instructions to each friend are independent of one another, and an instruction to one friend does not affect the movement of any other friend.

Takahashi wants to give instructions so that, after all friends have completed exactly T moves each, everyone is at the same coordinate. Only the final coordinates matter; whether friends are at the same coordinate during intermediate steps is irrelevant. The coordinate where everyone gathers is not predetermined and can be any coordinate.

Determine whether such a set of movement direction instructions exists. If it is possible, output Yes; if it is impossible, output No.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq T \leq 10^{18}
  • -10^{18} \leq X_i \leq 10^{18}
  • 1 \leq P_i \leq 10^9
  • All X_i are distinct
  • All inputs are integers

Input

N T
X_1 P_1
X_2 P_2
\vdots
X_N P_N
  • The first line contains an integer N representing the number of friends and an integer T representing the number of moves each friend makes, separated by a space.
  • The following N lines each contain, on the i-th line (1 \leq i \leq N), the initial coordinate X_i of friend i and a positive integer P_i representing the distance of each move, separated by a space.

Output

If all friends can gather at the same coordinate after exactly T moves each, output Yes; otherwise, output No on a single line.

Sample Input 1

3 2
0 1
2 1
4 2

Sample Output 1

Yes

Sample Input 2

2 1
0 1
3 1

Sample Output 2

No

Sample Input 3

6 5
4 2
13 3
5 1
22 4
35 5
3 7

Sample Output 3

Yes

Sample Input 4

15 1000000000000
0 1
-6 3
20 5
-700 7
2200 11
-1604928 13
11123440 17
-1000000000 1
2000000000 2
-3000000000 3
4000000000 4
-500000000000000000 500000000
600000000000000000 600000000
-999999998000000000 1000000000
999999996000000000 1000000000

Sample Output 4

Yes

Sample Input 5

1 1000000000000000000
-1000000000000000000 1000000000

Sample Output 5

Yes