题目描述

牛牛喝了 $10^{100000}$ 数量级的饮料，他得了一个需要去医院动手术的大病 —— 蛀牙。

但是和他一起去医院的总共有 $n$ 名患者。而这家医院只有一个医生和床位，所以只能同时给一个人做手术。每个人有一个病情严重度 $p_i$，保证所有人的严重度均不同，严重度越小说明所剩寿命越短，病情越紧急。

第 $i$ 名患者到达时间是 $t_i$，治病后会向医生付款 $a_i$ 个金币，手术时长是 $b_i$。假设第 $x$ 个单位时间开始手术，则第 $x+b_i-1$ 个单位时间结束手术，医生在第 $x+b_i$ 个单位时间及以后才能接待别的患者。手术过程不能中断。

患者到达医院之后可以不手术，先等待医生的通知（无论此时床位是否空闲），通知之后才进行手术。

如果一个患者发现医院里有一个病情严重度比自己轻微的患者正在手术而自己还没有进行手术，则他会开始医闹。医生不想让医闹发生，问他第 $k$ 个单位时间结束后能收获金币的最大值。

输入格式

第一行输入两个正整数 $n,k$。

第二行输入长度为 $n$ 的序列 $p_i$。

第三行输入长度为 $n$ 的序列 $t_i$。

第四行输入长度为 $n$ 的序列 $a_i。

第五行输入长度为 $n$ 的序列 $b_i$。

输出格式

输出一个数表示第 $k$ 个单位时间结束后能收获金币的最大值。

3 2
1 2 3
1 1 1
1 2 3
1 1 1

3

3 2
2 3 1
1 1 1
1 2 3
1 1 1

4

数据范围/提示

样例 $3$ 见附加文件。

$p_i$ 两两不同，$1≤ p_i≤ 𝑛$。

• 对于测试点 $1$：$1≤ 𝑛≤ 100,\ 1≤t_i,a_i,b_i,k≤ 10^9$。
• 对于测试点 $2\sim 5$：$1≤ 𝑛≤ 1000,\ 1≤t_i,a_i,b_i,k≤ 10^9$。
• 对于测试点 $6\sim 10$：$1≤ 𝑛≤ 10^5,\ 1≤t_i,a_i,b_i,k≤ 10^9$。