// 多重背包问题

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 10010;  // 这是物品的最大数量
const int MAXV = 10010;  // 这是背包的最大容量
int N;                   // 这是物品的种类
int V;                   // 这是背包容量
int weight[ MAXN ];      // 存储每件物品的重量，这里是存储已经进行二进制优化后的
int cost[ MAXN ];        // 这是每件物品的价值
int s[ MAXN ];           // 存储每件物品的数量
vector< int > dp( MAXV, 0 );

void knapsack()
{
    // 先遍历物品再遍历背包
    for ( int i = 1; i <= N; ++i )
    {
        for ( int j = V; j >= weight[ i ]; --j )
            dp[ j ] = max( dp[ j ], dp[ j - weight[ i ] ] + cost[ i ] );
    }
}

/**
 * @brief 多重背包问题与 0-1
背包问题不同的是，每个物品可以有多个副本，而不仅仅是一个。在最简单的实现方式中，我们可以将每个物品的每个副本都看作是一个独立的物品，但这样做会导致物品种类数目非常多，时间和空间复杂度都会大大增加，尤其当每个物品有很多副本时，复杂度变得不可接受。

2. 二进制优化
为了避免上述问题，使用二进制拆分法对多重背包进行优化。这个优化的核心思想是利用二进制的特性，将一个物品的数量拆分为若干个 2
的幂次方的组合，从而减少问题规模。

具体步骤如下：

二进制拆分： 假设某个物品有 n 件，二进制拆分的思路是将其拆分为多个数量为 1, 2, 4, 8, ... 的物品。

举例来说，如果某个物品有 13 件，我们可以将其拆分为 1 件、2 件、4 件和 6 件（其中 6 = 13 - (1 + 2 + 4)，即剩下的件数）。这样，13
件物品可以被表示为 1+2+4+6，这样的拆分减少了物品的种类数。 为什么使用二进制拆分： 通过二进制的特性，任意件数都可以由若干个 2
的幂次方之和表示。这样，我们通过拆分物品的数量，实际上减少了在背包中进行物品种类的数量，从而降低了复杂度。

扩展物品： 对于每一个物品，我们将其数量按照 2 的幂次方进行拆分，然后将拆分后的每一部分看作一个新的物品，这样我们就可以用 0-1
背包的方式处理这些“拆分出来的物品”了。
 *
 * @return int
 */
int main()
{
    // 存储实际
    int tempWeight[ MAXN ], tempCost[ MAXN ];
    int k = 0;  // 这里是存储展开后的下标的，因为如果一个数有n件，则会根据二进制优化来进行展开的
    cin >> N >> V;

    for ( int i = 1; i <= N; ++i )
        cin >> tempWeight[ i ];
    for ( int i = 1; i <= N; ++i )
        cin >> tempCost[ i ];
    // 然后就是进行二进制展开
    for ( int i = 1; i <= N; ++i )
    {
        cin >> s[ i ];
        for ( int j = 1; j <= s[ i ]; j <<= 1 )
        {
            k++;
            weight[ k ] = tempWeight[ i ] * j;
            cost[ k ] = tempCost[ i ] * j;
            s[ i ] -= j;  // 每次新优化一个就需要减去优化后的个数，当减去的s[i]的值小于了j是就说明不能该物品不能继续二进制优化了
        }
        if ( s[ i ] != 0 )
        {
            k++;
            weight[ k ] = tempWeight[ i ] * s[ i ];
            cost[ k ] = tempCost[ i ] * s[ i ];
        }
    }

    // 我们是将物品的件数，使用二进制优化，扩充为了物品的种类
    N = k;
    knapsack();
    cout << dp[ V ] << endl;
}