← 返回题目列表

AtCoder · awc0105_e

E. 集合点

中文机器翻译题面 查看原题

分数: 466 分

问题陈述

高桥正计划与 N 朋友们。高桥担任指挥官,向伙伴们发出行动指令。高桥本人不动,也不需要在集合地点。

的 N 朋友们在数轴上。朋友 i (1 \leq i \leq N) 最初位于坐标处 X_i。没有两个朋友共享相同的初始坐标。

每个朋友都表现得一模一样 T 按顺序移动。在朋友的一举一动中 i,或者 +P_i or -P_i 添加到其当前坐标。也就是说,如果移动之前的坐标是 c,移动后的坐标变为 c + P_i or c - P_i。选择不移动(位移 0) 是不允许的。

高桥可以自由指导每个朋友,对于他们的每一步棋,是否按 +P_i or -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
  • 第一行包含一个整数 N 代表好友数量,一个整数 T 代表每个朋友的移动次数,以空格分隔。
  • 以下 N 行各包含 i- 第行 (1 \leq i \leq N), 初始坐标 朋友的 X_i 朋友的 i 和一个正整数 P_i 代表每次移动的距离,以空格分隔。

输出

如果所有的朋友都可以在同一坐标处集合 T 各移动一次,输出 Yes;否则,输出 No 在一行上。


示例输入 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