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

Problem F. Black Cells

时间限制：1000ms

空间限制：256MB

题目描述

小周正在玩一个由 $10^{18}$ 个白色单元格组成的长条形游戏，这些单元格从左到右依次为 $0$ ,$1$ , $2$ ...。小周正在控制一个特殊指针，该指针最初位于 $0$ 单元格。此外，小周还可以按住一个 "Shift "按钮。

在一次移动中，小周可以执行三种操作之一：

• 将指针向右移动（从单元格 $x$ 移动到单元格 $x + 1$ ）；
• 按住 "Shift "键；
• 松开 "Shift "键：松开 "Shift "键时，所有在按下 "Shift "键时访问过的单元格都将变为黑色。

(当然，如果已经按住了 Shift 键，就不能再按了。同样，如果没有按下 Shift 键，也不能松开）。

小周的目标是为至少 $k$ 个单元格着色，但是有一个限制条件：有 $n$ 个区间段 $[l_i, r_i]$ ，小周只能为这些区间段内的单元格着色，也就是说，当且仅当 $l_i \le x \le r_i$ 时，小周才能为单元格 $x$ 着色。

要使至少 $k$ 个单元格着色为黑色，至少需要走多少步？

输入描述

第一行包含两个整数 $n$ 和 $k$ ( $1 \le n \le 2 \cdot 10^5$ ; $1 \le k \le 10^9$ )，分别代表区间数和所需的黑色单元格数。

第二行包含 $n$ 个整数 $l_1, l_2, \dots, l_n$ ( $1 \le l_1 \le l_2 \le \dots \le l_n \le 10^9$ )，其中 $l_i$ 表示第 $i$ 个区间段的左边界。

第三行包含 $n$ 个整数 $r_1, r_2, \dots, r_n$ （ $1 \le r_i \le 10^9$ ）。( $1 \le r_i \le 10^9$ ; $l_i \le r_i < l_{i + 1} - 1$ )，其中 $r_i$ 表示第 $i$ 个区间段的右边界。

输入的其他限制：

• 每个单元格最多属于一个区间

输出描述

输出至少要将 $k$ 个单元格染成黑色的最少步数，如果不可能，输出-1.

样例1

输入

2 3
1 3
1 4

输出

8

样例1解释

最佳操作顺序之一如下：

1. 向右移动：指针移动到 $1$ 单元格；
2. 按下 Shift 键；
3. 松开 Shift：单元格 $1$ 变为黑色；
4. 向右移动：指针移动到单元格 $2$ ；
5. 向右移动：指针移至单元格 $3$ ；
6. 按下 Shift 键；
7. 向右移动：指针移至单元格 $4$ ；
8. 松开 Shift：单元格 $3$ 和 $4$ 显示为黑色。

样例2

输入

4 20
10 13 16 19
11 14 17 20

输出

-1

样例2解释

我们最多只能为 $8$ 个单元格着色，而我们需要为至少 $20$ 个单元格着色。