‹ 上一题 下一题 ›

j02059. 盲盒系列选购 未做

题目描述

文具店有 个系列的盲盒。第 个系列有 款设计,其中第 款重 、喜爱值 。同一系列的多款设计外观冲突,每个系列至多买一款(也可以整系列不买)。你有一个承重上限为 的展示柜,求买下盲盒喜爱值总和的最大值。

输入格式

第一行两个整数 和 ,表示系列数与展示柜承重上限。接下来 个系列依次给出:每个系列第一行一个整数 表示该系列款数,接下来 行每行两个整数 和 ,表示该款盲盒的重量与喜爱值。

输出格式

一行一个整数,表示能获得的最大喜爱值总和。

样例

输入
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 。
输入
输出

            
答案