Description

有可供选择的实验集合$E$ ={$E$ $_1$ , $E$ $_2$ , …,$E$$_m$ }，进行这些实验需要使用的全部仪器集合$I$ ={$I$ $_1$ , $I$ $_2$ , …, $I$$_n$}。实验$E$$_j$ 需要用到的仪器是全部仪器集合的子集。配置仪器$I$$_k$ 的费用为$c$$_k$ 美元。实验$E$$_j$ 的赞助商为该实验结果支付$p$$_j$ 美元。需要确定进行哪些实验并配置哪些仪器才可以使净收益最大。净收益指进行实验所获得的全部收入与配置仪器的全部费用的差额。

Input

第$1$行包含两个正整数$m$ 和$n$ ，表示实验数和仪器数。接下来的$m$ 行，每行都是一个实验的有关数据，第$1$个数为赞助商同意支付该实验的费用，接着是该实验需要用到的若干仪器的编号。最后一行的$n$ 个数，表示配置每个仪器的费用。

Output

输出包括$3$行，第$1$行是实验编号，第$2$行是仪器编号，最后一行是净收益。

Samples

2 3
10 1 2
25 2 3
5 6 7

1 2
1 2 3
17

数据范围

$1 \leq n, m \leq 50$

来源

P2762