27317번 - 복슬복슬 여우꼬리

문제

일에 지친 한별이를 위로해주기 위해 천계에서 여우신이 내려왔어요! 여우신에게는 복슬복슬한 여우 꼬리가 있어 가만히 안고만 있어도 치유가 된다고 하네요.

다만 여우 꼬리는 특정 시간대에만 복슬복슬하고 그 이외의 시간에는 푸석푸석해지기 때문에 복슬복슬 마법을 통해 다시 복슬복슬하게 만들어주어야 해요!

여우신은 0ドル$시부터 $M$시까지 총 $M$시간 동안 지상에 내려와 있어요. 마법은 총 $K$번 사용할 수 있고 한 번 사용하면 $T$시간 동안 복슬복슬한 상태가 유지돼요. $K$번 이내로 마법을 사용하면서 한별이가 최대한 연속으로 복슬복슬하게 있을 수 있는 시간을 구해주세요.

복슬복슬 마법의 지속시간이 아직 끝나지 않았는데 복슬복슬한 시간대가 된다면 복슬복슬한 시간대에 들어간 시점에서 더 이상 복슬복슬 마법은 적용되지 않아요. 예를 들어, 복슬복슬한 시간대가 4ドル$시부터 6ドル$시까지라 가정하고, 3ドル$시에 7ドル$시간짜리 복슬복슬 마법을 썼다고 해도, 이 마법은 3ドル$시부터 4ドル$시까지만 적용이 돼요. 또한, 복슬복슬한 시간대에 복슬복슬 마법을 쓰는 경우에도 복슬복슬 마법은 즉시 취소가 돼요.

복슬복슬 마법을 쓰는 도중에 여우신이 천계로 돌아가야 할 시간이 되면 이 경우도 어쩔 수 없이 취소가 돼요. 예를 들어, 여우신이 9ドル$시에 복귀해야 하는데 7ドル$시에 3ドル$시간짜리 복슬복슬 마법을 썼다고 해도, 이 마법은 7ドル$시부터 9ドル$시까지만 적용이 돼요.

입력

첫 번째 줄에 복슬복슬한 시간대의 수 $N,ドル 문제에서 설명한 $M,ドル $K,ドル $T$가 공백으로 구분되어 주어져요. (1ドル\leq N\leq 100,円 000,ドル 1ドル \leq M \leq 10,円 000,円 000,ドル 1ドル\leq K\leq 100,円 000,ドル 1ドル\leq T\leq 10,円 000,円 000$)

두 번째 줄부터 $N+1$번째 줄까지 복슬복슬한 시간대 $X_i,ドル $Y_i$가 공백으로 구분되어 주어져요. (0ドル\leq X_i<Y_i\leq M$)

복슬복슬한 시간대는 서로 겹치지 않고 시간 순서대로 주어지며, 이전 복슬복슬이 종료하는 시간에 동시에 다음 복슬복슬이 시작하는 경우는 주어지지 않아요!

출력

한별이가 최대한 연속으로 복슬복슬할 수 있는 시간을 출력해주세요.

제한

힌트