fsl 的背包
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 512 M,其他语言1024 M
64bit IO Format: %lld

题目描述



众所周知,fsl非常擅长背包问题,这天fsl问了lbromine一道非常简单的背包问题。

fsl有 n 个物品,每个物品都有自己的体积和价值,现在fsl想要lbromine用一个背包装下其中的 k 件物品, lbromine找来了一个容量为 m 的背包,作为报酬,fsl打算将这 k 件物品中价值为这 k 件物品价值中位数的物品送给lbromine,现在lbromine想知道他能得到的最大价值物品的价值是多少,你能帮他解决这个问题吗?(如果背包无法装下 k 件物品,则输出 -1。)

输入描述:

输入第 1 行包含三个整数 nmk,分别表示物品总数,背包容量以及需要装下的物品数,其中,1\le k\le n\le10^6,1\le m\le10^9\textbf{注意:k为奇数!}

输入第 2 行包含 n 个整数,其中,w_i 表示第 i 个物品的体积 (1\le w_i\le10^9)

输入第 3 行包含 n 个整数 v_i,表示第 i 个物品的价值 (1\le v_i\le10^9)

输出描述:

输出一行,这一行只包含一个整数,表示答案;如果不能装下 k 件物品,输出 -1
示例1

输入

复制
5 10 3
1 2 3 4 5
1 2 3 4 5

输出

复制
4
示例2

输入

复制
3 3 3
1 1 4
5 1 4

输出

复制
-1