I Hate Ready to Program P10 - Graphics Galore: The Sequel

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

Finally. Now that you finished the ICS course, you're finally free! You can run home and delete that horrid app that has tried to ruin your life for good! But as you run happily away, out of the corner of your eye, you see someone jump towards you holding what seems to be a metal pan- the world fades...

You wake up in a room. It's cold in here... the stairs are in your view but you're tied down. ohi opens the door and walks downstairs. She asks you to help her with some CS work! "Why did she have to kidnap someone to do this? Can't she just ask someone?", you think to yourself. She shows you to a computer where she will let you code. On the computer, your worst fears come to life - Ready to Program is the only IDE available on that PC! And for some reason, the computer has no more storage for you to install another IDE!

You open the first assignment. Why is it in Notepad++? And why does this feel like CyperPatriot forensics? You brush the concerns aside. ohi tells you to open a file that reveals an overly large window of size P pixels, even bigger than the monitor dimensions. She explains she wants to make a basic colour palette onto the window. The colours are in bars, spanning from top to bottom. Overlapping colour bars will mix together to create a new colour. And she doesn't want too much mixing or it might create a completely different colour outside of the colour palette she wants! Determine how many pixel columns have less than C overlapping colours.

Constraints

1 \leq N \leq 10^5

1 \leq P \leq 10^9

1 \leq C \leq 10^3

1 \leq b_i, e_i \leq P

Input Specifications

The first line will contain 3 space-separated integers, N, P, and C.

The next N lines will contain 2 space-separated integers, b_i and e_i, the beginning and end of the ith colour bar, inclusive.

Output Specifications

Output an integer indicating how many columns of pixels have at least C overlapping colour bars.

Sample Input

3 1000 2
1 500
601 1000
1 1000

Sample Output

900

Sample Explanation

Only the pixel columns 501-600 inclusive only have 1 overlapping colour bar. All other pixels have 2 overlapping bars.


Comments

There are no comments at the moment.