分数: 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