该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在上一题中，牛牛喝了$10^100000$数量级的饮料，他得了一个需要去医院动手术的大病——蛀牙。但是和他一起去医院的总共有 𝑛 名患者。而这家医院只有一个医生和床位，所以只能同时给一个人做手术。每个人有一个病情严重度 $𝑝_𝑖$ ，保证所有人的严重度均不同，严重度越小说明所剩寿命越短，病情越紧急。

第 𝑖 名患者到达时间是 $t_𝑖$ ，治病后会向医生付款 $a_𝑖$ 个金币，手术时长是$b_𝑖$。

假设第 𝑥 个单位时间开始手术，则第𝑥 + $b_𝑖$ − 1个单位时间结束手术，医生在第 𝑥 + $b_𝑖$ 个 单位时间及以后才能接待别的患者。手术过程不能中断。

患者到达医院之后可以不手术，先等待医生的通知（无论此时床位是否空闲），通知之后才进行手术。 如果一个患者发现医院里有一个病情严重度比自己轻微的患者正在手术而自己还没有进行手术，则他会开始医闹。医生不想让医闹发生，问他第 𝑘 个单位时间结束后能收获金币的 最大值。

输入格式

输入包含五行。 第一两个正整数𝑛,𝑘。 第二行输入长度为𝑛的序列𝑝。 第三行输入长度为𝑛的序列𝑡。 第四行输入长度为𝑛的序列𝑎 第五行输入长度为𝑛的序列𝑏。 其中𝑛,𝑝,𝑡,𝑎,𝑏如题意所述。

输出格式

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

样例 1 输入

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

样例 1 输出

3

样例 2 输入

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

样例 2 输出

4

备注

$𝑝_𝑖$两两不同，1 ≤ $𝑝_𝑖$ ≤ 𝑛。 1 ≤ 𝑛 ≤ 100000,1 ≤ $t_𝑖$ $a_𝑖$ , $b_𝑖$ ,𝑘 ≤ 10 9