题目描述

豆包需要准备一场AC月赛，比赛需要至少包含 $n$ 道特定难度的题目，难度值分别为 $a_1, a_2, \dots, a_n$。

豆包已经准备了 $n$ 道题目，难度为 $b_1, b_2, \dots, b_n$。

豆包可以通过以下两种方式调整题目：

1. 免费调整：最多 $k$ 道题目免费调整（$0 \le k \le 1$），将难度从 $c$ 调整为任意 $d$，不产生成本。
2. 付费调整：其余题目若需要调整，将难度从 $c$ 调整到 $d$，调整成本为 $|c - d|$。

调整规则：

• 每道题目最多只能被调整一次（包括免费和付费调整）
• 总调整成本不能超过预算 $C$
• 不能新增题目（$k$ 仅表示免费调整次数）

请计算最少需要多少总调整成本才能满足比赛要求。如果无法满足要求，输出 -1。

输入格式

第一行包含三个整数 $n, k, C$，分别表示题目数量、免费调整次数和总预算。

第二行包含 $n$ 个非严格递增的整数 $a_1, a_2, \dots, a_n$，表示目标难度值。

第三行包含 $n$ 个非严格递增的整数 $b_1, b_2, \dots, b_n$，表示初始难度值。

输出格式

输出一个整数，表示最少需要的总调整成本。如果无法满足要求，输出 -1。

输入输出样例

3 0 5
5 10 15
8 12 18

-1

样例 $\tt \#1$说明

• $8→5(成本3)、12→10(成本2)、18→15(成本3)$，总成本 $8 >$ 预算 $5$。不成立，输出 -1。

3 1 5
2 3 8
4 9 11

2

样例 $\tt \#2$说明

• 免费将 $11$ 修改为 $2$，$4→3(成本1)、9→8(成本1)$。总成本 $2 \le$ 预算 $5$。

数据范围

• $10\%$ 的数据，$1 \le n \le 100, 1 \le C \le 10^3, 1 \le a_i, b_i \le 10^3, k = 0$
• 另 $20\%$ 的数据，$1 \le n \le 100, 1 \le C \le 10^3, 1 \le a_i, b_i \le 10^3, k = 1$
• 对于 $100\%$ 的数据，$1 \le n \le 10^4, 1 \le C \le 10^{18}, 1 \le a_i, b_i \le 10^9, k \in [0, 1]$