EOJ-自适应编程学习平台

在提瓦特大陆上，K 位旅行者正准备前往深渊挑战，每位旅行者都有一个独立的背包，容量均为$V$。存在$N$件圣遗物，被分为$M$类。（保证每个圣遗物都属于且只属于一个类别，保证每个类别都有物品）。每个圣遗物都有一个容量$v_i$和战斗增益$p_i$，关于圣遗物与背包，存在以下规则：

• 每个圣遗物在一个背包中最多只能被选择一次
• 但同一个圣遗物可以出现在多个背包
• 同类型的圣遗物在一个背包中最多只能被选择一次。

你现在需要为每个人找到一个不同的方案，使得k个旅行者总战斗增益最大。当两个人的方案存在一个圣遗物不同时，两个方案不同。

如果合法方案数不足$K$，则空方案的战斗增益为**-1**。

第1行4个整数：$K$、$V$、$N$、$M$

第2~N+1行2个整数：每个圣遗物的容量$v_i$和战斗增益$p_i$

第N+2~N+M+1行：

​ 首先输入一个整数$num$，随后紧跟$num$个整数，表示第$i$类包含的圣遗物列表

$1\le K \le 100$

$1 \le V \le 10^5$

$1 \le N \le 500$

$1 \le M \le 500$

$0 \le v_i \le V, 0\le p_i \le 10^6$

一个整数，最后的答案