Gas Station - Repovive Starter Round 1 | Repovive

7E. Gas Station

2500 pts2s256 MB

Repovive has built a gas station with several one-way lines.

There are $n$ cars. Car $i$ needs exactly $a_i$ minutes to refuel, and must leave the gas station no later than $b_i$ minutes after the process starts.

At the beginning, all lines are empty. The cars enter the gas station in the order $1,2,\ldots,n$ . When a car enters, it must choose one of the lines and join the back of that line. Therefore, inside each line, the order of cars is the same as the order in which they entered the gas station.

All cars start refueling immediately after entering their chosen line. Cars in all lines can refuel at the same time. However, a car cannot leave before all cars in front of it in the same line have left.

More formally, suppose one line contains cars $p_1,p_2,\ldots,p_m$ from front to back. Then car $p_j$ leaves at time

\max(a_{p_1},a_{p_2},\ldots,a_{p_j}).

An assignment of cars to lines is valid if every car $i$ leaves at time at most $b_i$ .

Find the minimum possible number of lines $k$ such that there exists a valid assignment of the cars to exactly $k$ lines.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le b_i \le 10^9$
The sum of $n$ over all test cases is at most $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ b_1 \quad b_2 \quad \cdots \quad b_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} k \end{array} \right\} \times t

Samples

Input

Case 1

1
5
5

Case 2

3
2 5 4
2 5 5

Case 3

4
4 3 2 1
4 3 2 1

Case 4

4
10 1 9 1
10 1 10 1

Case 5

5
3 2 1 5 4
3 2 1 5 5

Explanation

Case 1

There is only one car, so one line is enough.

Case 2

If all cars are placed in one line, their leaving times are $2$ , $5$ , and $5$ . All of them leave before their deadlines.

Case 3

Each car has a smaller deadline than every car before it needs for refueling. Therefore, no car can stand behind an earlier car, so four lines are needed.

Case 4

Use one line for cars $1$ and $3$ , and another line for cars $2$ and $4$ . Their leaving times are valid. One line is not enough because car $2$ would have to leave too late.

Case 5

Three lines are enough: put cars $1$ , $4$ , and $5$ in one line, car $2$ in another line, and car $3$ in another line. The first three cars cannot be handled with fewer than three lines.

Output

Case 1

Case 2

Case 3

Case 4

Case 5

Repovive has built a gas station with several one-way lines.

There are $n$ cars. Car $i$ needs exactly $a_i$ minutes to refuel, and must leave the gas station no later than $b_i$ minutes after the process starts.

More formally, suppose one line contains cars $p_1,p_2,\ldots,p_m$ from front to back. Then car $p_j$ leaves at time

\max(a_{p_1},a_{p_2},\ldots,a_{p_j}).

An assignment of cars to lines is valid if every car $i$ leaves at time at most $b_i$ .

Find the minimum possible number of lines $k$ such that there exists a valid assignment of the cars to exactly $k$ lines.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le b_i \le 10^9$
The sum of $n$ over all test cases is at most $2 \times 10^5$

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ b_1 \quad b_2 \quad \cdots \quad b_n \end{array} \right\} \times t

\left. \begin{array}{l} k \end{array} \right\} \times t

If all cars are placed in one line, their leaving times are $2$ , $5$ , and $5$ . All of them leave before their deadlines.

Use one line for cars $1$ and $3$ , and another line for cars $2$ and $4$ . Their leaving times are valid. One line is not enough because car $2$ would have to leave too late.

Three lines are enough: put cars $1$ , $4$ , and $5$ in one line, car $2$ in another line, and car $3$ in another line. The first three cars cannot be handled with fewer than three lines.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

7E. Gas Station

Constraints

Input

Output

Samples

7E. Gas Station

Constraints

Input

Output

Samples