时间限制： 1.0 秒

空间限制： 256 MB

题目描述

David 有一个制造工厂，工厂里有 $n$ 名工人。工厂接受了一个大订单，包括 $m$ 种产品，其中第 $i$ 种产品需要 $a_i$ 个。

由于工人擅长的工艺不同，每个工人都只能制作其中的一些产品。让工人工作需要发工资，由于每个工人的能力不同，工资也是不同的，让第 $i$ 名工人每制作一件产品，就需要付 $b_i$ 的工资。

然而事情并没有这么简单，如果一名工人没有安排工作，他就没有收入，会生气地找 David 麻烦，同样的，如果一名工人被安排的工作过多，他就无法完成任务，也会生气地找 David 麻烦。还好 David 对自己的工人足够了解，他知道第 $i$ 名工人可接受的生产产品个数的范围是 $[l_i,r_i]$，即如果工人 $i$ 被安排的产品件数小于 $l_i$ 或大于 $r_i$ 都会产生麻烦。

David 想知道，他能否完成订单的要求，如果可以，他最少需要给工人多少工资才能完成。

输入格式

从标准输入读入数据。

第一行输入两个整数 $n,m$，含义如题面所示。

第二行输入 $m$ 个整数 $a_i$，含义如题面所示。

第三行输入 $n$ 个整数 $b_i$，含义如题面所示。

接下来 $n$ 行，每行输入两个整数 $l_i,r_i$，依次表示每个工人可接受的产品数量范围。

接下来 $n$ 行，每行输入若干个整数，首先输入一个整数 $k_i$，表示该工人可以生产的产品种类数，接下来输入 $k_i$ 个整数，依次表示该工人可以生产的产品种类编号。

输出格式

输出到标准输出。

输出一行一个整数，如果无法满足订单要求，输出 $-1$，否则输出David要付的最小工资。

3 2
5 10
5 6 3
1 10
5 6
2 5
1 1
1 2
2 1 2

70

子任务

对于 $20\%$ 的数据，有 $1\leq n,m\leq 5,\sum\limits_{i=1}^m a_i\leq 20$。

对于另外 $20\%$ 的数据，有 $l_i=0$。

对于 $100\%$ 的数据，有：

• $1\leq n,m\leq 250$；
• $1\leq a_i\leq 100$；
• $1\leq b_i\leq 500$；
• $0\leq l_i\leq r_i\leq \sum\limits_{i=1}^m a_i$。