#P3660. JabberwockyII

JabberwockyII

题目描述

给定三个长度为 NN 的数列 X,A,BX,A,B。选取一个下标序列

1=p0<p1<⋯<pm−1=N.1=p_0<p_1<\cdots<p_{m-1}=N.

对每一对相邻下标 u=pi−1u=p_{i-1} 和 v=piv=p_i,若 Xv≤XuX_v\le X_u,这一段的权值为 AuA_u;否则为 BuB_u。整个子序列的权值是各段权值的和。

把所有满足条件的子序列按权值从小到大排列,求第 KK 个子序列的权值。不同子序列即使权值相同,也分别占一个名次。

输入格式

第一行两个整数 N,KN,K。

接下来三行,每行 NN 个整数,分别给出数列 X,A,BX,A,B。

输出格式

输出一行一个整数,表示第 KK 小的子序列权值。

样例

8 10
8 8 6 6 9 9 0 8
-8 4 2 1 -4 -1 -7 1
6 -7 -7 6 7 5 -4 8
-19

数据范围

1≤N≤200011\le N\le 20001,1≤K≤1061\le K\le 10^6,且至少有 KK 个符合要求的子序列。所有输入整数及所求答案都在有符号 3232 位整数范围内。