T316497 数论高手

题目描述

赤耳报名 div2 就像去健身房办卡，报名每次都有他，但是从来没有过一次行动。

“我今晚必打！”赤耳又点击了报名按钮。

鸡尾酒实在看不下去了，便对赤耳说：“你再不训练就会从巨佬变成菜鸡啊！”

赤耳不信，说“我 DP 会开数组，图论会连边，数论会整除，凭什么说我菜？”

鸡尾酒说“给你一个长度为 $n$ 的序列，请你找出一个子序列，使得子序列的和可以被 $m$ 整除。请开始表演？”

赤耳蒙了，他从没做过这么难的整除题，请你帮帮他。

第一行输入三个整数 $n,m,k$ 。 $(m \leq n \leq 10^{18},k \leq 2*10^5)$ ，代表鸡尾酒总共给出了 $n$ 个数字，需要选出一些数字使得这些数字之和能被 $m$ 整除

接下来有 $k$ 行，每行两个整数 $a,b$ ，描述鸡尾酒给出的数字。 $a_i,b_i$ 代表鸡尾酒给了 $b_i$ 个大小为 $a_i$ 的数字。保证 $b_1+b_2+...+b_k=n。(0 \leq ai \leq 10^{18})$

如果可以找出一个方案满足要求，输出Yes，否则输出No

5 3 2
5 1
4 4

Yes

鸡尾酒给出了包含1个5，4个4的序列，则可以选择其中三个4作为子序列，和为12，可以被3整除，输出Yes。