You are given two sorted integer arrays a and b, each of length n, where the i-th interval is [a[i], b[i]].

Two intervals are considered connected if they overlap or share at least one endpoint. A connected set is a maximal collection of intervals such that every interval is connected to every other interval through a chain of overlapping intervals.

You are also given an integer k.

You may add exactly one new interval [L, R], where

L and R are integers, L ≤ R, R - L ≤ k.

The added interval may overlap with any number of existing intervals and can connect multiple connected sets into one.

Return the minimum number of connected sets that can remain after adding the new interval optimally.

Function Signature int minimumConnectedSets(vector<int>& a, vector<int>& b, int k); Constraints 1 ≤ n ≤ 2 × 10^5 0 ≤ a[i] ≤ b[i] ≤ 10^9 a is sorted in non-decreasing order. b is sorted in non-decreasing order. 0 ≤ k ≤ 10^9 Example

Input

a = [1, 5, 8] b = [2, 6, 9] k = 3

The existing intervals are

[1,2] [5,6] [8,9]

Initially, there are 3 connected sets.

You can add the interval

[2,5]

which has length 3.

It connects the first two sets:

[1,2] -- [2,5] -- [5,6]

while [8,9] remains separate.

Hence the minimum number of connected sets is

2

Similarly, adding

[6,8]

also results in 2 connected sets by merging the last two sets.