Skip to content

11587: 【原1587】抽选活动

题目

题目描述

author: chonps 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1587

Description

抽选活动是个无底洞。

一个抽选活动的奖品除了限定商品以外，还有其它抽选活动的参加资格。

kuma 先生调查了最近 BS96 的所有抽选活动。深知自己非洲血统的他经过数据分析掌握了所

有活动获得奖品所需要的氪金量。

现在 kuma 先生想知道自己最多能获得多少价值的限定商品，但因为他需要去筹集资金所以

这个问题就交给你了。

Input Format

第一行两个数 n, m。表示抽选活动的数量和 kuma 先生筹集到的资金。

接下来 n 行，每行先有 2 个数，表示拿到奖品需要的氪金量，和限定商品的价值。之后可能

会跟若干数 ai，表示可以获得编号为 i 的抽选活动的参加资格。

没有出现在任何一个奖品中的活动是可以直接参加的。

保证每个活动的参加资格最多出现一个活动的奖品中，而且没有依赖环。

Output Format

一个数，表示能获得的最大价值。

Sample Input

10 20
15 83
6 51 8
16 77 7
16 81
7 98 2 6 4
2 54 9
12 50
15 10 3 10 1
4 30
6 27

Sample Output

233

Limits

  • 30%, n <= 11
  • 70%, n <= 1000, m <= 100
  • 100%, n <= 1000, m <= 10000

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！