Black Cells
Contest: Educational Codeforces Round 147 (Rated for Div. 2)
Difficulty rating: 1900
Tags: binary search, brute force, greedy, math

You are playing with a really long strip consisting of $$$10^{18}$$$ white cells, numbered from left to right as $$$0$$$, $$$1$$$, $$$2$$$ and so on. You are controlling a special pointer that is initially in cell $$$0$$$. Also, you have a "Shift" button you can press and hold.

In one move, you can do one of three actions:

- move the pointer to the right (from cell $$$x$$$ to cell $$$x + 1$$$);
- press and hold the "Shift" button;
- release the "Shift" button: the moment you release "Shift", all cells that were visited while "Shift" was pressed are colored in black.

Your goal is to color at least $$$k$$$ cells, but there is a restriction: you are given $$$n$$$ segments $$$[l_i, r_i]$$$ — you can color cells only inside these segments, i. e. you can color the cell $$$x$$$ if and only if $$$l_i \le x \le r_i$$$ for some $$$i$$$.

What is the minimum number of moves you need to make in order to color at least $$$k$$$ cells black?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 10^9$$$) — the number of segments and the desired number of black cells, respectively.

The second line contains $$$n$$$ integers $$$l_1, l_2, \dots, l_n$$$ ($$$1 \le l_1 < l_2 < \dots < l_n \le 10^9$$$), where $$$l_i$$$ is the left border of the $$$i$$$-th segment.

The third line contains $$$n$$$ integers $$$r_1, r_2, \dots, r_n$$$ ($$$1 \le r_i \le 10^9$$$; $$$l_i \le r_i < l_{i + 1} - 1$$$), where $$$r_i$$$ is the right border of the $$$i$$$-th segment.

Additional constraints on the input:

- every cell belongs to at most one segment;
- the sum of $$$n$$$ doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print the minimum number of moves to color at least $$$k$$$ cells black, or $$$-1$$$ if it's impossible.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first test case, one of the optimal sequences of operations is the following:

1. Move right: pointer is moving into cell $$$1$$$;
2. Press Shift;
3. Release Shift: cell $$$1$$$ is colored black;
4. Move right: pointer is moving into cell $$$2$$$;
5. Move right: pointer is moving into cell $$$3$$$;
6. Press Shift;
7. Move right: pointer is moving into cell $$$4$$$;
8. Release Shift: cells $$$3$$$ and $$$4$$$ are colored in black.

In the second test case, we can color at most $$$8$$$ cells, while we need $$$20$$$ cell to color.

In the third test case, one of the optimal sequences of operations is the following:

1. Move right: pointer is moving into cell $$$1$$$;
2. Move right: pointer is moving into cell $$$2$$$;
3. Move right: pointer is moving into cell $$$3$$$;
4. Press Shift;
5. Move right: pointer is moving into cell $$$4$$$;
6. Move right: pointer is moving into cell $$$5$$$;
7. Release Shift: cells $$$3$$$, $$$4$$$ and $$$5$$$ are colored in black.

Example input:
4
2 3
1 3
1 4
4 20
10 13 16 19
11 14 17 20
2 3
1 3
1 10
2 4
99 999999999
100 1000000000

Example output:
8
-1
7
1000000004

Editorial:
Let's look at what's happening in the task: in the end the pointer will move into some position $$$p$$$ and some segments on the prefix $$$[0, p]$$$ will be colored. Note that it's optimal to stop only inside some segment (or $$$l_i \le p \le r_i$$$ for some $$$i$$$), and if we colored $$$x$$$ segments (including the last segment $$$[l_i, p]$$$ that may be colored partially) the answer will be equal to $$$p + 2 \cdot x$$$.
Let's prove that it's not optimal to skip segments with length $$$len = r[i] - l[i] + 1 \ge 2$$$. By contradiction, suppose the optimal answer $$$a$$$ has a skipped segment $$$[l_i, r_i]$$$. If we color that segment instead, we will make $$$2$$$ more moves for pressing and releasing Shift, but we can make at least $$$len$$$ right move less. So the new answer $$$a' = a + 2 - len \le a$$$ — the contradiction.
Now we are ready to write a solution. Let's iterate over $$$i$$$ — the last segment we will color (and therefore the segment where we stop). At first, let's imagine we colored the whole segment $$$[l_i, r_i]$$$ as well. Let $$$s$$$ be the total length of all segments on prefix $$$[0, r_i]$$$ that are longer than $$$1$$$ and $$$c$$$ be the number of segments of length $$$1$$$ on this prefix.
There are three cases:
• if $$$s + c < k$$$, stopping inside the $$$i$$$-th segment is not enough;
• if $$$s < k$$$ but $$$s + c \ge k$$$, we will color all "long" segments plus several short ones. The current answer will be equal to $$$r_i + 2 ((i - c) + (k - s))$$$, where $$$r_i$$$ is where we stop, $$$(i - c)$$$ is the number of long segments and $$$(k - s)$$$ is the number of short segments we need;
• if $$$s \ge k$$$, then we don't need any short segments. More over, we can stop even before reaching $$$r_i$$$. So, the current answer will be equal to $$$r_i - (s - k) + 2 (i - c)$$$, where $$$r_i - (s - k)$$$ is the exact position to stop to get exactly $$$k$$$ black cells and $$$(i - c)$$$ is the number of long segments.
The answer is the minimum among the answers we've got in the process. Since it's easy to update values $$$s$$$ and $$$c$$$ when we move from $$$i$$$ to $$$i + 1$$$, the total complexity is $$$O(n)$$$.