logo AlgoBeat OnlineJudge
登录 注册

#102122. [BZOJ 2122] 工作评估

内存限制:259 MiB 时间限制:50000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

利用空闲时间,BX 希望外出工作,工作开始之前,公司就会给 BX 一个评估值 ,之后每天 BX 的评估值都是根据上一天的评估值和当天公司的运行状况得出,即 ,但是每天的评估值有一个上限,也就是说完整的评估公式因该是 。现在 BX 已经知道了该公司对自己的初始评估值 、公司每天的运行状况 、每天的评估上限 ,他的空闲时间是从第 天到第 天,他希望找到一段时间 ,使得从第 天开始工作,到第 天结束后的评估值最大。当然如果任意一段时间的工作得到评估值都小于初始评估值 ,BX 可以选择不工作,从而得到最大的评估值。

输入格式

输入的第一行包含两个整数 ,分别表示总共工作天数和询问数。
第二行 个数,表示
第三行 个数,表示
以下 行,每行 个数 ,表示一次询问。

输出格式

行,每行输出一个整数,表示评估的最大值

样例输入

6 3
-6 5 3 2 -3 4
8 10 8 1 9 9
1 3 9
2 6 3
3 4 0

样例输出

10
8
3

数据范围与提示

对于 数据,满足