时空限制
1S/512M
题目描述
有 n 个知识点,第 i 个知识点的价值为 ai,复习难度为 bi,遗忘度为 ci。
复习知识点所花的时间与复习顺序有关,具体来说,如果第 i 个知识点被排在第 j 位复习,那么需要花费 bi+j∗ci 的时间。
求花费时间不超过 t 的前提下,恰好复习 m 个知识点的最大价值和。
如果无法在 t 时间内复习 m 个知识点,输出 −1。
格式
输入格式
第一行包含三个整数 n,m,t,分别表示知识点数量、需要复习的知识点数量和时间限制。
第二行包含 n 个整数 ai,分别表示每个知识点的价值。
第三行包含 n 个整数 bi,分别表示每个知识点的复习难度。
第四行包含 n 个整数 ci,分别表示每个知识点的遗忘度。
输出格式
输出一个整数表示花费时间不超过 t 的前提下,恰好复习 m 个知识点的最大价值和。如果无法在 t 时间内复习 m 个知识点,输出 −1。
样例
样例输入 #1
样例输出 #1
样例解释 #1
按 3,1,4 的顺序复习,所需时间为 (3+4×1)+(4+2×2)+(2+2×3)=23,价值和为 3+2+4=9。
样例输入 #2
样例输出 #2
样例解释 #2
按 5,3,4 的顺序复习,所需时间为 (5+10×1)+(3+4×2)+(2+2×3)=34,价值和为 5+3+4=12。
数据规模
对于 100% 的数据, 1≤m≤n≤40,0≤t≤1018,1≤ai≤1015,0≤bi,ci≤1015。
测试点编号 |
n |
特殊性质 |
1 |
≤10 |
无 |
2~3 |
≤20 |
ci=0 |
4~5 |
无 |
6~10 |
≤40 |