bLue祝你元宵节快乐!

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

元宵节到了,bLue 从超市采购了 n 种汤圆准备好好享受一下。

他买回来的 n 种汤圆,每种都有 3 个属性:单个汤圆能提供的愉悦值 a、购买数量 b、每碗最多可以容纳汤圆的个数 c。

不过,bLue 的饮食习惯略奇特,他的饭量可以一次吃 m 碗汤圆,但是每碗的汤圆必须全部是同一种汤圆且必须装满一碗(即汤圆个数等于此类汤圆的最大容纳量 c),否则他就不会吃。

那么问题来了,bLue 应该如何下这 m 碗汤圆,才能使他获得的总愉悦值最高?

Input

输入数据有多组(数据组数不超过 100),到 EOF 结束。

对于每组数据:

  • 第 1 行包含 2 个整数 n, m (1 <= n, m <= 100),表示汤圆种类数和 bLue 最多能吃的碗数。
  • 第 2 行包含 n 个用空格隔开的整数 ai (0 <= ai <= 100),表示每种汤圆的单个可获得的愉悦值。
  • 第 3 行包含 n 个用空格隔开的整数 bi (0 <= bi <= 100),表示每种汤圆的购买数量。
  • 第 4 行包含 n 个用空格隔开的整数 ci (1 <= ci <= 100),表示每种汤圆的在一碗内的最大容纳量。

Output

对于每组数据,输出 1 行,包含 1 个整数,表示 bLue 能获得的最大愉悦值。

Sample Input

3 3
1 2 3
5 4 2
2 2 3
2 5
4 1
2 0
1 1

Sample Output

10
8

Hint

Source

【2017年寒假集训 阶段测试赛2 - 元宵节专场】bLue