P3823果冻怪 | ||
|
问题描述
小南和小开在三友路上养了很多只果冻怪。我们可以将三友路想象成一根长度无限的数 轴,在这上面生活着n只果冻怪。每经过一秒,一只果冻怪便会分裂成两只。具体来说,一 只坐标为x的果冻怪,会分裂成两只分别在(x − 1),(x + 1)上的果冻怪,并且原来在x上的果 冻怪会消失。 由于生存空间有限,若一个位置上有不少于P只果冻怪,那么会立刻消失 P 只。经过测 定P = 10^9 + 7。 小南和小开想知道在第T秒末,位置w有多少只果冻怪。初始时刻是0秒初。
输入格式
第一行为三个整数,n,T,w。含义如题所述。
接下来 n 行,每行两个整数𝑥𝑖,𝑐𝑖,表示𝑥𝑖位置,有𝑐𝑖只果冻怪。注意𝑥𝑖可能有重复。
输出格式
输出一个非负整数,表示 T 秒末 w 位置上的果冻怪个数
样例输入
2 2 2
0 3
1 2
样例输出
3
提示
对于 30%的数据: 1 ≤ n ≤ 100,1 ≤ T ≤ 16。
对于 60%的数据:1 ≤ n ≤ 10^5,1 ≤ T ≤ 16。
对于 100%的数据:1 ≤ n,T,𝑐𝑖 ≤ 10^5,0 ≤ |𝑤|,|𝑥𝑖| ≤ 10^5。
来源 WJJ