No submission language available for this problem.

Background

Special for beginners, ^_^

Description

关小山挖到了 n 种矿物。但他的纳戒空间不太够（纳戒，类似背包），他必须选择一些矿物带回去。

现在纳戒还有 w 个区域，每个区域最多容纳 64 个相同种类的矿物。每种矿物都有一个价值，关小山想要让带回去的矿物价值之和最大，问这个最大价值。

Format

Input

第一行两个正整数 n, w，代表矿物种类和纳戒区域个数。

第二行 n 个正整数 ai，代表第 i 种矿物的数量。

第三行 n 个正整数 vi​，代表第 i 种矿物的价值。

Output

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

Samples

4 2
23 60 23 10
1 10 20 100

1600

10 100
36 41 84 98 54 35 40 56 98 36
9910 2705 8511 2148 6498 4467 5632 8296 5779 8217

3452340

Limitation

1s, 1024KiB for each test case.