P1005：牛客/2025-6/H 背包问题

题目描述

有 $n$ 种物品，每种物品个数无限，有体积 $a_i$ 和价值 $b_i$ 两种属性。

定义 $f(v)$ 为：你有一个体积为 $v$ 的背包，要求选择若干个物品放入背包中，使物品的总价值最大，且背包中物品的总体积不超过背包的容量。

给定这 $n$ 种物品和一个数 $V$，计算 $\sum_{v=1}^{V} f(v)\bmod 998244353$。

输入输出格式

输入

第一行包含两个正整数 $n\ (1\le n\le 10^5)$，和 $V\ (1\le V\le 10^{18})$。
接下来 $n$ 行，每行包含两个正整数 $a_i\ (1\le a_i\le 1500)$ 和 $b_i\ (1\le b_i\le 10^9)$，表示每种物品的属性。

输出

输出一个数，表示答案。

样例

5 10
7 9
5 3
1 1
2 4
9 10

105

10 20
4 11
10 13
6 11
10 1
5 8
9 13
7 7
13 8
3 13
7 6

819

数据范围

• $1\le n\le 10^5$
• $1\le V\le 10^{18}$
• $1\le a_i\le 1500$
• $1\le b_i\le 10^9$