27689번 - Two covers 서브태스크다국어

In a typical genome assembly problem, we are given set of small strings called pieces and our task is to find their superstring with some reasonable properties. In this problem, you are given one such superstring and a collection of pieces aligned to that superstring. Your task is to evaluate one particular property.

You are given the length of the superstring ℓ, a list of n pieces, and a number k. The positions in the superstring are numbered from 1 to ℓ. For each piece i you are given the positions (b_i, e_i) of its beginning and end.

The letter at position x in the superstring is well-covered if:

• There is a piece (b_i, e_i) such that b_i ≤ x − k and x ≤ e_i.
• There is a different piece (b_j, e_j) such that b_j ≤ x and x + k ≤ e_j.

Your task is to count the number of letters which are not well-covered.

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

Each test case starts with a line containing three integers: ℓ, n, and k. Each of the following n lines contains two integers b_i and e_i (1 ≤ b_i ≤ e_i ≤ ℓ): the indices of the endpoints of a piece. The pairs (b_i, e_i) are all distinct.

For each test case, output a single line with a single integer – the number of letters that are not well-covered.

The well-covered letters are at positions 3, 4, and 5. Note that the letter at position 6 is not well-covered.