17258번 - 인기가 넘쳐흘러

욱제는 세계적인 인기를 자랑하는 월클(World Class) 스타이다! 영선이는 욱제TV 구독자 5조5억명 달성 기념 파티를 준비하고 있다. 영선이는 욱제를 아는 수많은 사람들에게 초대장을 돌렸는데, 초대장을 받은 모든 사람들이 자신이 언제 와서 언제 떠날 것인지 답변을 줬다.

욱제는 월클병에 걸려서 기대에 미치지 않는 인원과 파티를 즐기는 것을 용납하지 않는다. 그래서 욱제는 자신을 제외한 파티 인원이 T명 미만이 되는 순간 파티장에서 나가고, 파티 인원이 T명 이상이 되는 순간 다시 돌아온다. 답변을 정리하던 영선이는 충격적인 사실을 깨달았는데, 파티가 진행되는 동안 T명 이상의 인원이 계속 유지되지 못 한다는 것이다. 그래서 영선이는 급히 자신의 친구들 K명을 부르려고 한다.

영선이의 친구들은 부끄럼이 많아서 욱제 및 영선이의 친구들을 제외한 파티 인원이 T명 이상이 되는 순간 다 같이 파티장에서 나가 버리고 돌아오지 않는다. 또한 파티 인원이 T명 이상이면 영선이의 친구들은 파티장에 들어가지 않는다. 단, 아직 들어오지 않은 영선이의 친구들은 이후 파티 인원이 T명 미만이 되면 파티장으로 들어 갈 수 있다. 영선이는 친구들 각각을 적절한 시각에 투입시켜 최대한 오랫동안 욱제가 파티에 머물도록 하고 싶다. 꼭 K명을 모두 투입시킬 필요는 없다. 영선이는 욱제를 얼마나 오래 파티에 머물게 할 수 있을까?

첫째 줄에 파티가 진행되는 시간 N (1 ≤ N ≤ 300), 파티에 초대한 사람 수 M (1 ≤ M ≤ 300), 영선이의 친구 수 K (1 ≤ K ≤ 300), 욱제가 기대하는 최소의 파티 인원 T (1 ≤ T ≤ M)가 주어진다.

둘째 줄부터 M개의 줄에 걸쳐 각 줄마다 a_i, b_i가 주어진다. i번째 사람은 시각 a_i에 파티에 참여하고, 시각 b_i에 파티를 떠난다. (1 ≤ a_i ≤ N, a_i < b_i ≤ N + 1)

파티가 시작되는 시각은 1을 기준으로 한다.

영선이의 친구들을 파티에 투입시켰을 때 욱제가 파티에 머무를 수 있는 최대 시간을 출력한다.