题目描述
文具店有 个系列的盲盒。第 个系列有 款设计,其中第 款重 、喜爱值 。同一系列的多款设计外观冲突,每个系列至多买一款(也可以整系列不买)。你有一个承重上限为 的展示柜,求买下盲盒喜爱值总和的最大值。
输入格式
第一行两个整数 和 ,表示系列数与展示柜承重上限。接下来 个系列依次给出:每个系列第一行一个整数 表示该系列款数,接下来 行每行两个整数 和 ,表示该款盲盒的重量与喜爱值。
输出格式
一行一个整数,表示能获得的最大喜爱值总和。
样例
输入
3 8 2 3 4 4 5 2 2 3 5 6 1 6 10
输出
13
数据范围
- 对于 30% 的数据: 5 且 Σk_i 15, 800(可爆搜每系列选哪款)。
- 对于 60% 的数据: 50 且 Σk_i 150, 3000。
- 对于 100% 的数据: 200 且 Σk_i 500(1 50), ,1 ,1 。