题目描述

巫师想考验辰辰，便给了他一个幻境。在幻境里，辰辰会依次经过 N 个山洞，并有选择地在一些山洞里采集草药。每棵草药都有自己的价值，不同的草药可能需要不同的采集时长。巫师只给了辰辰有限的时间 H ，并要求他在这有限的时间内，采集到总价值最大的草药。

当然，从一个山洞走到下一个山洞需要一些时间。如果他在前几个山洞逗留太久，可能没有时间经过后几个山洞。或者，如果后几个山洞里并没有特别有价值的草药，他也可以只在前几个山洞里采药。

如果你是辰辰，你是否会被这样的任务难倒呢？

——给出 N 个山洞分别的草药数量 $m_i$，每棵草药的价值 $v_{i,j}$ 和采集这棵草药需要的时间 $t_{i,j}$ ，以及从每一个山洞走到下一个山洞需要的时间 $p_i$ ，请你计算出在时间 H 内能采集到草药价值总和的最大值。

输入格式

第 1 行，包含两个整数，山洞个数 N 和时间限制 H。

第 2 行，包含 N−1 个整数，第 i 个数表示从第 i 个山洞走到第 i+1 个山洞需要的时间 $p_i$ 。

接下来 N 行，依次描述 N 个山洞的信息——每行第一个整数 $m_i$ ，表示相应山洞的草药数量；接着 $2\times m_i$ 个整数，两两一组，表示一棵草药的价值 $v_{i,j}$ 和采集这棵草药需要的时间 $t_{i,j}$ 。

输出格式

一个整数，表示在时间限制 H 内能采集到草药价值总和的最大值

样例输入

3 21
6 8
2 1 3 2 4
2 5 2 8 2
2 10 1 20 1

样例输出

43

提示

对于 100% 的数据，$1\le N\le 20$，$0\lt H\le 5,000$，$5\le p_i\le 2,000$，$\sum p_i\le H$，$0\lt m_i\le 100$，$0\lt v_{i,j},t_{i,j}\le 200$。

其中：

至少 50% 的数据，山洞个数 $N=1$，此时，数据第 2 行为空，第 3 行为山洞的具体信息；

至少 15% 的数据，山洞个数 $N=1$，且该山洞中的草药数量$m_{1}\le 10$；

至少 75% 的数据，山洞个数 $N\le 10$。

1 1

1 1 1

1

3 21
6 8
2 1 3 2 4
2 5 2 8 2
2 10 1 20 1

43

3 20
6 8
2 1 3 2 4
2 5 2 8 2
2 10 1 20 1

43