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

题目描述

河面上从左到右分布着 $n$ 个停靠点，编号为 $1$ 到 $n$。第 $i$ 个停靠点附近的水流高度为 $h_i$，在该停靠点停靠还需要支付 $c_i$ 点费用。

小船从第 $1$ 个停靠点出发，目标是到达第 $n$ 个停靠点。

每次可以从停靠点 $i$ 向右移动到停靠点 $j$，但必须满足：

从停靠点 $i$ 移动到停靠点 $j$ 的费用为：

其中，第 $1$ 个停靠点的停靠费用不需要支付。

有些停靠点已经损坏，不能到达或停留，但第 $1$ 个和第 $n$ 个停靠点保证可以使用。

求小船从第 $1$ 个停靠点到达第 $n$ 个停靠点的最小总费用。如果无法到达，输出 -1。

输入格式

输入第一行 $n,k$。第二行 $n$ 个高度 $h_i$，第三行 $n$ 个停靠费用 $c_i$，第四行 $n$ 个整数 $b_i$；$b_i=1$ 表示损坏。保证 $b_1=b_n=0$。

输出格式

输出到达第 $n$ 个停靠点的最小费用；若无法到达，输出 -1。

样例 1

5 2
1 4 2 8 3
0 2 3 1 4
0 0 0 1 0

9

样例说明

无

数据范围

$2\le n\le5000,1\le k<n,0\le h_i,c_i\le10^9$。

本题共有 20 个测试点，每个测试点 5 分。