思路:动态规划-分组背包

本问题等价于 有一个容积为$m$的背包，现有$n$组物品，每组有三个物品，第$i$组物品为:

物品1:价值$a_i$,体积$0$

物品2:价值$b_i$,体积$1$

物品3:价值$c_i$,体积$2$

题目内容

塔子哥有$n$个魔法石，初始时魔法石的价值为$a_i$.塔子哥还有$m$点能量。对于每个能量，它可以用来点亮一颗魔法石。第$i$个魔法石第一次被点亮后的价值为$b_i$，魔法石也可以被再次点亮，价值进而变为$c_i$.请问塔子哥该如何安排手中的能量，使得魔法石的价值总和最大呢？

输入描述

第一行两个整数$n$,$m$ ($1 \leq n \leq 1000 , 0 \leq m \leq 1000$) , 分别代表魔法石的个数以及能量数量.

第二行$n$个整数:$a_1,a_2,...,a_n$ , 代表这$n$个魔法石初始价值

第三行$n$个整数:$b_1,b_2,...,b_n$ , 代表这$n$个魔法石第一次被点亮后的价值

第三行$n$个整数:$c_1,c_2,...,c_n$ , 代表这$n$个魔法石第二次被点亮后的价值

$0 \leq a_i , b_i , c_i \leq 1e9$

输出描述

一行整数，代表最大价值。

样例1

输入

3 3
1 2 3
3 1 1
100 1 1

输出

105

样例2

输入

3 2
100 1 0
1 1 1
3 100 1

输出

200