题目描述

W教授正在为国家航天中心计划一系列的太空飞行。

每次太空飞行可进行一系列商业 性实验而获取利润。

现已确定了一个可供选择的实验集合$\red{E=\{E_1，E_2，…，E_m\}}$，和进行这 些实验需要使用的全部仪器的集合$\red { I=\{I_1，I_2，…I_n\} }$。

实验$\red{E_j}$需要用到的仪器是$\red I$的子集$\red {R_j}$。

配置仪器$\red {I_k}$的费用为$\red {c_k}$美元。

实验$\red{E_j}$的赞助商已同意为该实验结果支付$\red {p_j}$美元。

W教授的 任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才 能使太空飞行的净收益最大。

这里净收益是指进行实验所获得的全部收入与配置仪器的全部 费用的差额。

*编程任务： 对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。

输入格式

第$\red 1$行有$\red 2$ 个正整数$\red m$和$\red n$。

$\red m$是实验数，$\red n$是仪器数。

接下来的$\red m$ 行，每行是一个实验的有关数据。

第一个数赞助商同意支付该实验的费用；

接着是该实验需要用到的若干仪器的编号。

最后一行的$\red n$个数是配置每个仪器的费用。

输出格式

第$\red 1$ 行是实验编号；

第$\red 2$ 行是仪器编号；

最后一行是净收益。

样例

输入样例

2 3
10 1 2
25 2 3
5 6 7

输出样例

1 2
1 2 3
17

提示

$\red{n,m \le 50}$