时空限制

1S/512M

题目描述

有 $n$ 个知识点，第 $i$ 个知识点的价值为 $a_i$，复习难度为 $b_i$，遗忘度为 $c_i$。

复习知识点所花的时间与复习顺序有关，具体来说，如果第 $i$ 个知识点被排在第 $j$ 位复习，那么需要花费 $b_i+j*c_i$ 的时间。

求花费时间不超过 $t$ 的前提下，恰好复习 $m$ 个知识点的最大价值和。

如果无法在 $t$ 时间内复习 $m$ 个知识点，输出 $\text{−1}$。

格式

输入格式

第一行包含三个整数 $n,m,t$，分别表示知识点数量、需要复习的知识点数量和时间限制。

第二行包含 $n$ 个整数 $a_i$，分别表示每个知识点的价值。

第三行包含 $n$ 个整数 $b_i$，分别表示每个知识点的复习难度。

第四行包含 $n$ 个整数 $c_i$，分别表示每个知识点的遗忘度。

输出格式

输出一个整数表示花费时间不超过 $t$ 的前提下，恰好复习 $m$ 个知识点的最大价值和。如果无法在 $t$ 时间内复习 $m$ 个知识点，输出 $\text{−1}$。

样例

样例输入 #1

5 3 28
2 1 3 4 5
4 5 3 2 5
2 1 4 2 10

样例输出 #1

9

样例解释 #1

按 $3,1,4$ 的顺序复习，所需时间为 $(3+4\times 1)+(4+2\times 2)+(2+2\times 3)=23$，价值和为 $3+2+4=9$。

样例输入 #2

5 3 34
2 1 3 4 5
4 5 3 2 5
2 1 4 2 10

样例输出 #2

12

样例解释 #2

按 $5,3,4$ 的顺序复习，所需时间为 $(5+10\times 1)+(3+4\times 2)+(2+2\times 3)=34$，价值和为 $5+3+4=12$。

数据规模

对于 $100\%$ 的数据， $1\leq m\leq n\leq 40$，$0\leq t\leq10^{18}$，$1\leq a_i\leq 10^{15}$，$0\leq b_i,c_i\leq 10^{15}$。

测试点编号	$n$	特殊性质
1	$\leq 10$	$\text{无}$
2~3	$\leq 20$	$c_i=0$
4~5		$\text{无}$
6~10	$\leq 40$