17980번 - Alehouse 다국어

문제

Making friends can seem impossible, but going to the alehouse makes it easy — it is actually the only way to make friendships. Luckily, the alehouse is extremely good at its task: if two people are inside simultaneously, they instantly become friends. People even become friends if they meet each other in the door as one leaves and one enters the alehouse!

In Consistentville, each of its n residents goes to the alehouse exactly once each week, and always during the same milliseconds as the week before. This is convenient for everyone, since then nobody needs to befriend new people all the time, which can be quite exhausting.

You are contemplating a move to Consistentville in order to adopt their well-ordered lifestyle, and have decided that you want as many friends as possible. However, you don’t actually enjoy ale that much, so you decide to limit your weekly visit at the alehouse to at most k milliseconds. What is the maximum number of friends you can get?

입력

The first line of input contains two positive integers n (1 ≤ n ≤ 100 000), and k (0 ≤ k < 604 800 000). The next n lines describe at which millisecond each of the original residents of Consistentville enters and leaves the alehouse every week. Specifically, the i^th line consists of two integers a_i and b_i (0 ≤ a_i ≤ b_i < 604 800 000) indicating that the i^th resident enters the alehouse at millisecond a_i and leaves the alehouse at millisecond b_i each week.

출력

A single integer, the maximum number of friends you can get.

제한

힌트