Description

在上一题中， 牛牛喝了$10^{100000}$ 数量级的饮料， 他得了一个需要去医院动手术的大病——蛀 牙。 但是和他一起去医院的总共有 n 名患者。而这家医院只有一个医生和床位， 所以只能同时 给一个人做手术。每个人有一个病情严重度 pi ，保证所有人的严重度均不同，严重度越小 说明所剩寿命越短，病情越紧急。 第 i 名患者到达时间是 ti， 治病后会向医生付款 ai 个金币， 手术时长是 bi 。假设第 x 个 单位时间开始手术， 则第x + bi − 1个单位时间结束手术， 医生在第 x + bi 个 单位时间及以 后才能接待别的患者。手术过程不能中断。 患者到达医院之后可以不手术，先等待医生的通知(无论此时床位是否空闲)， 通知之后才 进行手术。 如果一个患者发现医院里有一个病情严重度比自己轻微的患者正在手术而自己还没有进行 手术， 则他会开始医闹。医生不想让医闹发生， 问他第 k 个单位时间结束后能收获金币的 最大值。

Input Format

输入包含五行。 第一行输入两个正整数n, k。 第二行输入长度为n的序列p。 第三行输入长度为n的序列t。 第四行输入长度为n的序列a。 第五行输入长度为n的序列b。 其中n, p, t, a, b如题意所述。

Output Format

输出一个数表示第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

Hint

• pi 两两不同， $1 ≤ pi ≤ n$。
• 对于测试点1： $1 ≤ n ≤ 100,1 ≤ ti , ai , bi , k ≤ 10^9$ 。
• 对于测试点2~ 5： $1 ≤ n ≤ 1000,1 ≤ ti , ai , bi , k ≤ 10^9$ 。
• 对于测试点6~ 10： $1 ≤ n ≤ 100000,1 ≤ ti , ai , bi , k ≤ 10^9$ 。