Oh, no! Shahid in trouble. He’s got himself stuck in a cave (we don’t know how) and is looking for a way out.

The bigger problem is that he needs to get his tractor out of the cave (don’t ask why Shahid owns a tractor!). He currently faces a large block of height N cells and length N cells, and needs to get his tractor across this block.

The block is made up of vertical columns of soil, each of which is one cell long. Each column has a continuous vertical gap, with the ith column having its gap from the lith cell to the hith cell (starting from the bottom, 0-indexing).

That is, in the ith column, there is no soil from the lith cell to the hith cell (both inclusive).

Shahid can build additional gaps by clearing some cells of soil. His tractor has height H, and therefore, he needs to build a horizontal corridor of height H passing through all the columns. That is, some consecutive H rows must have no soil. Please see the figures in the example and explanation sections for more details.

Shahid is able to clear one cell of soil by spending one unit of energy.

Shahid is smart, and will figure out a way to build the horizontal corridor while spending the minimum possible amount of energy.

find out what is the minimum possible energy he needs to spend.

**Input:**
First line of input contains one integer T - number of test cases. T test cases follow.
Each test case starts with two integers N and H – size of the cave and height of the tractor, respectively.
In each of the next N lines are two integers li and hi, respectively indicating lowest and highest number of cell for the gap in the ith column.
**Output:**
Print a single integer representing minimum energy required.

#include <stdio.h> long long p[1000005][2]; int main() { int t; long n,h,i,a,b; register int c; scanf("%d",&t); while(t--) { scanf("%ld %ld",&n,&h); for(i=0;i<n;i++) p[i][0]=p[i][1]=0; for(i=0;i<n;i++) { scanf("%ld %ld",&a,&b); p[a][0]++; p[b][1]++; } for(i=0;i<n;i++) p[i+1][0]=p[i+1][0]+(p[i][0]-p[i][1]); for(i=0;i<n;i++) p[i][0]+=p[i-1][0]; c=p[h-1][0]; for(i=0;i<n;i++) { if(c<p[i][0]-p[i-h][0]) c=p[i][0]-p[i-h][0]; } printf("%lld\n",(long long)h*n-c); } return 0; }

**INPUT_1:**

1

6 3

3 2

2 4

1 5

3 5

1 4

2 2

**OUTPUT:**

6

**INPUT_2:**

2

4 2

1 2

2 1

1 3

3 3

5 4

4 3

3 4

2 3

3 1

1 2

**OUTPUT:**

4

15

**ILLUSTRATION (MIND BOGGLING)**

**Morae Q!**

- Find the number of strings made by using each alphabet as starting character.
- Find the Pythagorean triplet.
- Find out what is the minimum possible energy he needs to spend.
- Sort the array in non-decreasing order and print out the original indices of sorted array.
- Compute the number of landmasses on the planet after all the meteorites have fallen.
- Give the appropriate server status as output.
- Regular expressions (Regex) using search module in python.
- Find the minimum distance between any pair of equal elements in the array.
- Find the total number of matching pairs of socks that are available.
- Find the total number of teams which can work together and cannot work together.
- Given the heights of all the boys and girls tell whether it is possible for all boys to get a girl.
- Find the sequence of cities to visit according to coordinates and conditions.
- Find the number of unique patches of rectangular land to grow samba(rice) in.
- Regular expression Regex matching strings.
- Generate a greeting quote for admin.
- Find all the cavities on the map and replace their depths with the character X.
- Check whether the given graph is Bipartite or not.
- Find the status of the passengers and safari cars at zoo after k units of time.
- Determine the chair number occupied by the child who will receive that chocolate.
- Check if Rubik’s cube of any dimensions can be assembled.