预算查询（budget）

题目描述

某公司准备从一批项目中选择若干个进行投资。

公司记录了连续 (m) 天的基础投入成本，第 (i) 天的成本为 $(a_i)$。

共有 (n) 个候选项目。

第 (i) 个项目由三个整数 $(L_i,R_i,v_i)$ 描述。

项目的投入成本为对应日期区间内每天成本之和，完成后可以获得 $(v_i)$ 的收益。

每个项目最多只能选择一次。

不同项目相互独立，即使对应日期存在重叠，也可以同时选择，但费用分别计算。

现在公司需要回答 (Q) 次独立的预算查询。

每次查询给出一个预算 (B)，要求计算在总投入成本不超过 (B) 的情况下，可以获得的最大总收益。

每次查询均从全部候选项目中重新选择，不受其他查询结果影响。

输入格式

第一行包含四个整数：

m n V Q

其中 (V) 表示所有查询可能出现的最大预算。

第二行包含 (m) 个正整数 $(a_i)$。

接下来 (n) 行，每行三个整数 $(L_i,R_i,v_i)$。

最后 (Q) 行，每行包含一个整数 (B)，表示一次预算查询。

输出格式

输出 (Q) 行，每行一个整数，表示对应预算下的最大收益。

输入输出样例 #1

输入

6 4 11 5
2 1 2 3 1 2
1 2 5
3 4 9
5 6 6
2 5 11
2
3
6
8
11

输出

0
6
11
15
20

样例解释

四个项目的实际成本分别为 3、5、3、7。

例如：

• 预算为 2 时，没有项目可以选择，最大收益为 0。
• 预算为 6 时，可以选择第 1、3 个项目，获得收益 11。
• 预算为 11 时，可以选择第 1、2、3 个项目，总成本为 11，总收益为 20。

数据范围

• $(1\le m\le10^5)$
• $(1\le n\le100)$
• $(1\le V\le2000)$ -$(1\le Q\le10^5)$
• $(1\le a_i\le1000)$
• $(1\le L_i\le R_i\le m)$
• $(1\le v_i\le10000)$
• $(0\le B\le V)$