话说 Nan 在海边等人，预计还要等上 分钟。为了打发时间，他玩起了石子。 Nan 搬来了 堆石子，编号为 ，每堆包含 颗石子。每 分钟，Nan 会在编号在 之间的石堆中挑出任意 颗扔向大海（好疼的玩法），如果 剩下石子不够 颗，则取尽量地多。为了保留扔石子的新鲜感，Nan 保证任意两个区间 和 ，不会存在 的情况，即任意两段区间不存在包含关系。可是，如果选择不当，可能无法扔出最多的石子，这时 Nan 就会不高兴了。所以他希望制定一个计划，他告诉你他 分钟打算扔的区间 以及 。现在他想你告诉他，在满足前 分钟都取到你回答的颗数的情况下，第 分钟最多能取多少个石子。
第一行正整数 ，表示石子的堆数；
第二行正整数 ，，；
有等式 ；
第三行正整数 ，表示有 分钟；
第四行正整数 ，，；
有等式 。
接下来 行，每行两个正整数 。
有 行，第 行表示第 分钟最多能取多少石子。
5 3 2 4 7 3 2 5 2 6 4 9 2 4 1 2 3 5
2 5 5
对于 的数据，，，，
石子每堆个数分别为 。
第 分钟，从第 到第 堆中选 个；
第 分钟，从第 到第 堆中选 个；
第 分钟，从第 到第 堆中选 个，但最多只能选 个。
