暂无测试数据。

在一个长度为 $n$ 的序列上，每个位置摆着一颗宝石，一共有 $\dfrac n 2$ 种宝石，每种宝石恰好两颗，每颗宝石有一个重量且都为整数，同种宝石的重量相同。

你可以随意选定一个起点，然后从起点出发在序列上行走。每走一步，你耗费的体力值就是携带的宝石的总重量，走到一个位置时，如果该位置有宝石，你可以选择收集这个宝石或什么都不做，如果你同时携带了两颗同种类型的宝石，那么这两颗宝石就会发生配对并消失。

这个序列有些特殊，每个位置只能走至多 $k$ 次（一开始站在起点算一次），你想要知道，收集所有宝石使它们配对需要的最小体力值是多少？

输入格式

第一行两个整数 $n,k$，保证 $n$ 是偶数。

第二行 $n$ 个整数，表示序列上每个位置的宝石种类。

第三行 $\dfrac n 2$ 个整数，表示每种宝石的重量。

输出格式

输出一个整数表示需要的最小体力值。

数据范围

对于前 $20\%$ 的数据，有 $n\leq 10,k=10^9$。

对于前 $40\%$ 的数据，有 $n\leq 10^3,k=10^9$。

对于另外 $20\%$ 的数据，保证所有宝石的重量之和 $\leq 1$。

对于 $100\%$ 的数据，有 $1\leq n\leq 10^6,1\leq k\leq 10^9,1\leq a_i\leq \dfrac n 2,0\leq w_i\leq 10^6$，其中 $a_i$ 表示第 $i$ 颗宝石的种类，$w_i$ 表示第 $i$ 种宝石的重量。

2 2
1 1
3

3