题目描述

某天，赫罗发现自己完全没有实现项目的经验。于是他决定花一整年的时间完成一些项目，一边积累经验一边赚钱。

赫罗已经完成了全年的所有项目，现在只需要确定这些项目的执行顺序。

共有 $n$ 个项目，其中 $n$ 为偶数。第 $i$ 个项目由两个正整数 $a_i$ 和 $b_i$ 组成。完成项目 $i$ 时，会按顺序发生两件事：

1. 完成该项目的实现环节，赫罗的经验值增加 $a_i$；
2. 项目全部完成后结算所得，本次剩余金额为 $b_i\times E$，其中 $E$ 是结算时赫罗当前的原始经验值。

除此之外，赫罗还有一项额外安排：在恰好完成 $\frac{n}{2}$ 个项目之后，他会去参加一场训练营。训练营只会让他的经验值增加 $X$，不会产生任何收入。

初始时，赫罗的经验值和收入均为 $0$。请你计算，赫罗通过合理安排项目执行顺序，全年最多能获得多少总收入。

输入格式

第一行输入两个整数 $n$ 和 $X$，分别表示项目数量和训练营增加的原始经验值。

第二行输入 $n$ 个整数 $a_i$，表示完成对应项目后增加的经验值。

第三行输入 $n$ 个整数 $b_i$，表示对应项目的结算系数。

数据范围

• $2\le n \le 50$，且 $n$ 为偶数；
• $1\le a_i\le 100000$；
• $1\le b_i\le 10$；
• $0\le X\le 100000$。

输出格式

输出一个整数，表示赫罗全年能够获得的最高总收入。

样例

样例 1

输入：

4 10
3 2 5 4
4 1 3 2

输出：

173

说明：一种最优顺序为：项目 2、项目 4、训练营、项目 3、项目 1。

• 项目 2 后 $E=2$，收入 $1\times 2=2$；
• 项目 4 后 $E=6$，收入 $2\times 6=12$；
• 训练营后 $E=16$；
• 项目 3 后 $E=21$，收入 $3\times 21=63$；
• 项目 1 后 $E=24$，收入 $4\times 24=96$。 总收入 $2+12+63+96=173$。

样例 2

输入：

4 100
4 4 6 6
2 2 3 3

输出：

726

样例 3

输入：

12 62
38 13 28 59 26 62 48 75 6 69 94 51
4 6 4 5 4 3 1 5 6 5 2 2

输出：

22288

数据范围与子任务

\begin{array}{|c|c|c|c|} \hline \textbf{子任务} & \textbf{测试点编号} & \textbf{分值} & \textbf{特殊限制} \\ \hline 1 & 1\sim 2 & 10 & n \lt 20 \\ \hline 2 & 3\sim 4 & 10 & X = 0 \\ \hline 3 & 5\sim 6 & 10 & \textbf{所有 }b_i = 1 \\ \hline 4 & 7\sim 12 & 30 & \textbf{所有 }a_i \lt 10 \\ \hline 5 & 13\sim 20 & 40 & \textbf{无特殊限制} \\ \hline \end{array}