1897. [国家集训队2011]工作评估

【问题描述】

【输入格式】

【输出格式】

【样例输入】

【样例输出】

【数据规模和约定】

【问题描述】

    利用空闲时间，BX希望外出工作，工作开始之前，公司就会给BX一个评估值X₀，之后每天BX的评估值都是根据上一天的评估值和当天公司的运行状况得出，即X_i=X_i-1+D_i,但是每天的评估值有一个上限，也就是说完整的评估公式因该是X_i=min{X_i-1+D_i,L_i}。

    现在BX已经知道了该公司对自己的初始评估值X₀、公司每天的运行状况Di、每天的评估上限Li，他的空闲时间是从第A天到第B天，他希望找到一段时间i，j (A≤i≤j≤B)，使得从第i天开始工作，到第j天结束后的评估值最大。当然如果任意一段时间的工作得到评估值都<初始评估值X₀，BX可以选择不工作，从而得到最大的评估值。

【输入格式】

    输入的第一行包含两个整数N、M，分别表示总共工作天数和询问数。

    第二行N个数，表示D_i。

    第三行N个数，表示L_i。

    以下M行，每行3个数A、B、X₀，表示一次询问。

【输出格式】

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

【样例输入】

    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

【数据规模】

    对于30%数据，满足N,M<101

    对于60%数据，满足N,M<10001

    对于100%数据,满足N,M<50001,|D_i|<10001,0≤L_i<1000000001