问题 A: 小A的游戏任务系列一

问题 A: 小A的游戏任务系列一

时间限制: 1 Sec  内存限制: 128 MB
提交: 1067  解决: 131
[状态] [讨论版] [提交] [命题人:]
题目描述
小A最近爱上打游戏,今天他计划要通关一个高难度的副本,副本内有N个任务,它们有串行关系和并行关系,串行关系是指多个任务依次被完成,并行关系是指多个任务只需完成一个即可。小A经过查阅攻略,了解到每个任务需消耗a_i秒完成,并且N个任务中有M组并行任务,小A最快多久能通关?
输入
第一行输入两个整数N,M,分别代表任务个数和并行任务的组数。(1<=N<1e6, 0<=M<=10000)
接下来N行,每行输入两个整数包含ID,a_i分别代表任务ID和完成该任务需要的时间。(1<=ID<=1e6, 1<=a_i<=1e9)
接下来M行,每行首先输入一个整数K,代表当前组内并行任务的个数,接下来k个整数,代表并行任务的ID。(2<=K<=100)数据保证两个不同的ID不会重复出现。
输出
小A通关需要的时间。
样例输入 Copy
10 2
1 3
2 5
3 6
4 7
5 8
6 2
7 9
8 1
9 1
10 5
2 4 5
3 2 3 7
样例输出 Copy
24