Internet Problem Solving Contest

IPSC 2014

Problem T – 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.

Problem specification

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 (bi, ei) of its beginning and end.

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

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

Input specification

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 bi and ei (1 ≤ bi ≤ ei ≤ ℓ): the indices of the endpoints of a piece. The pairs (bi, ei) are all distinct.

In the easy subproblem T1 you may assume that t ≤ 20, ℓ ≤ 10 000, n ≤ 1000, and 1 ≤ k ≤ ℓ.

In the hard subproblem T2 you may assume that t ≤ 10, ℓ ≤ 1017, n ≤ 1 000 000, and 1 ≤ k ≤ ℓ.

Output specification

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




8 3 2
1 4
3 5
4 8



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