Background

Keep faith and hope for the future. Make your most sincere dreams, and when the opportunities come, they will fight for them. It may take a season or more, but the ending will not change. Ambition, best, become a reality. An uncertain future, only one step at a time, the hope can realize the dream of the highest. We must treasure the dream, to protect it a season, let it in the heart quietly germinal. However, we have to gently protect our hearts deep expectations, slowly dream, will achieve new life.

Description

猫猫头是一名魔法师，现在猫猫头想制作一种神奇的马卡龙macaron，制作一件马卡龙需要$n$种材料，第$i$种材料需要$a_i$个,猫猫头需要按照$b_1,b_2,b_3,...,b_n$的顺序依次放入这$n$种材料，当猫猫头放了$m$种材料之后(此时剩下(n-m)种材料还未加入)，猫猫头意识到他可以施展一次魔法，将剩下的某一种材料变多，变成$520^{1314}$个那么多（你不用担心猫猫头怎么放得下的，毕竟猫猫头是魔法师，有个次元口袋也是很正常的），猫猫头现在对于$1～n$种材料分别有$c_1,c_2,c_3,...,c_n$个，猫猫头想知道他最多可以获得多少马卡龙。

Warning：猫猫头不想重复做一样的事情，所以制作流程只会执行一次，猫猫头可以一次性制作若干马卡龙

Format

Input

第一行有两个数字$n(1 \le n \le 5 \cdot 10^5),m(1 \le m \le n)$

下面有三行，每行有$n$个数

第一行代表$a_1,a_2,a_3,...,a_n(1 \le a_i \le 10^9)$

第二行代表$b_1,b_2,b_3,...,b_n(1 \le b_i \le 10^9)$

第三行代表$c_1,c_2,c_3,...,c_n(1 \le c_i \le 10^9)$

Output

输出一个数字，代表最多能获得多少个马卡龙

Samples

input

5 2
1 2 3 4 5
1 2 3 4 5
10 9 8 8 6

output

2