Lumber Jack and Sick Leaves

Little Lumber Jack has a good reputation in his family. He is said to have never missed one class in school!

He is now in the final year, ready to graduate, and he has a big issue. His friend, who was usually providing him with sick leaves, messed up and gave him a lot more sick leaves than he needed. Some of them even overlap!

Lumber Jack is in trouble, he can't take the sick leaves to his teacher like this because he would get suspicious. Neither should there be sick leaves that don't cover any day he was absent in, nor ones that overlap. Help Jack find a minimal subset of the sick leaves that satisfy those requirements, in order to preserve his reputation.


On the first line of the input there are 3 integer numbers, D, N and M, where D is the number of days in the school year, N represents the number of days skipped by Lumber Jack and M denotes the number of sick leaves he has.

On the second line of the file there will be N integer numbers, separated by space, representing the days skipped.

The next M lines contain one pair of integer numbers each, X and Y, denoting the start and end days of the leave.


A single integer number, denoting the minimum number of sick leaves Jack has to take in order to cover all the days he skipped school.

It is guaranteed that a solution will exist.


  • 1 ≤ ND, X, Y, M ≤ 1000


9 4 6
2 4 5 8
1 3
2 3
3 4
2 5
5 6
7 8

Sponsors Gold