题目描述Description

在一个城市里，有一家批发公司，该公司有 n​ 个货仓，m​ 个用户。

每天，该公司为每个货仓 i（1 ≤ i ≤ n）提供 W_{i} 吨货物，而每个用户 j（1 ≤ j ≤ m ）需要 X_{j} 吨货物。

货仓 i 只能向集合 M_{i} 中的用户发送货物，并且货仓 i 每天最多只能向用户 j ∈ M_{i} 发送 w_{i,j} 吨货物。

最近，该公司修建了一些道路，使得货仓 i（1 ≤ i < n）能将最多 Y_{i} 吨多余的货物运送到货仓 i + 1 ，以便供应需要更多货物的用户。

问在修建完道路后，该公司每天最多可以向用户发送多少吨货物。

输入格式Input

第一行包括两个整数 n，m（1≤n, m≤500），表示货仓个数和用户个数。

第二行包括 n 个整数 W_{i}（1 ≤ W_{i} ≤ 1000），表示每个货仓收到的货物吨数。

第三行包括 m 个整数 X_{j}（1 ≤ X_{j} ≤ 1000），表示每个用户需要的货物吨数。

接下来的 n 行，每行先输入一个整数 t_{i}（1 ≤ t_{i} ≤ m），表示集合 M_{i} 的大小。随后输入 t_{i} 对整数 （j, w_{i, j}）（1≤j≤m，1≤w_{i, j}≤100），表示货仓 i 最多能将 w_{i, j} 吨货物发给用户 j。

最后一行，输入 n - 1 个整数 Y_{i}（1 ≤ Y_{i} ≤ 50），表示货仓 i（1≤i<n） 最多能向货仓 i + 1 提供的货物吨数。

输出格式Output

一个整数，表示该公司每天最多能发给用户的货物吨数。

样例Sample

提示Hint

用户 j​ 在该公司买不够 X_{j} 吨货物的话，也无所谓噢，反正又不止一家批发公司！

出题Author

Owaiter

来源Source