Overflowing Popularity
Time limit1sMemory limit256 MB
Given M guests with arrival and departure times, choose when to insert up to K extra friends so that the count of ordinary attendees stays below T as long as possible.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Greedy, Intervals, Implementation
- Solved
- No attempts yet
Problem
Wookje is a world-class star with global popularity! Youngsun is preparing a party to celebrate reaching 5 trillion 5 hundred million subscribers on WookjeTV. Youngsun sent invitations to countless people who know Wookje, and everyone who received an invitation replied with when they will arrive and when they will leave.
Wookje has come down with world-class syndrome, so he refuses to enjoy a party with fewer people than he expects. Therefore, the moment the number of party attendees excluding himself drops below T, he leaves the party hall, and the moment the number of attendees reaches T or more, he comes back. While organizing the replies, Youngsun realized something shocking: the number of attendees cannot stay at T or more throughout the party. So Youngsun hurriedly decides to call K of his friends.
Youngsun's friends are shy, so the moment the number of party attendees excluding Wookje and Youngsun's friends reaches T or more, they all leave the party hall together and do not come back. Also, if the number of party attendees is T or more, Youngsun's friends do not enter the party hall. However, friends who have not yet entered can enter the party hall later once the number of party attendees drops below T. Youngsun wants to send each of his friends in at an appropriate time so that Wookje stays at the party as long as possible. He does not have to send in all K friends. How long can Youngsun make Wookje stay at the party?
Input
The first line gives the duration of the party N (1 ≤ N ≤ 300), the number of people invited to the party M (1 ≤ M ≤ 300), the number of Youngsun's friends K (1 ≤ K ≤ 300), and the minimum number of party attendees Wookje expects T (1 ≤ T ≤ M).
From the second line, M lines follow, each giving ai and bi. The i-th person joins the party at time ai and leaves the party at time bi. (1 ≤ ai ≤ N, ai < bi ≤ N + 1)
The party starts at time 1.
Output
Print the maximum time Wookje can stay at the party when Youngsun sends his friends in.