술집
면접 대비시간 제한1초메모리 제한512 MB
일주일을 나타내는 원 위에 n개의 닫힌 구간이 주어질 때, 길이가 k 이하인 구간 하나를 골라 최대한 많은 구간과 겹치도록 하는 문제이다.
문제
친구를 사귀는 일은 불가능해 보일지도 모르지만, 술집에 가면 쉽다. 사실 술집에 가는 것이 친구를 사귀는 유일한 방법이다. 다행히 술집은 제 역할을 아주 잘한다. 두 사람이 동시에 술집 안에 있으면 그 즉시 친구가 된다. 한 사람이 나가고 다른 사람이 들어오면서 문에서 마주쳐도 친구가 된다!
Consistentville에는 n명의 주민이 살고 있고, 각 주민은 일주일에 한 번 술집에 가며, 항상 지난주와 같은 밀리초에 간다. 그래서 아무도 계속 새 친구를 사귈 필요가 없으니 모두에게 편리하다. 새 친구를 사귀는 일은 꽤 지칠 수 있기 때문이다.
당신은 그들의 질서 정연한 생활 방식을 따르려고 Consistentville로 이사를 갈까 고민 중이며, 친구를 최대한 많이 사귀고 싶어 한다. 하지만 맥주를 그렇게 좋아하지는 않아서, 일주일에 술집에 머무는 시간을 최대 k밀리초로 제한하려고 한다. 얻을 수 있는 친구 수의 최댓값은 얼마인가?
입력
첫째 줄에 양의 정수 n (1 ≤ n ≤ 100 000)과 k (0 ≤ k < 604 800 000)가 주어진다. 다음 n개 줄에는 Consistentville의 기존 주민 각각이 매주 술집에 들어오고 나가는 밀리초가 주어진다. 구체적으로 i번째 줄에는 두 정수 ai와 bi (0 ≤ ai ≤ bi < 604 800 000)가 주어지며, 이는 i번째 주민이 매주 ai밀리초에 술집에 들어와 bi밀리초에 나간다는 뜻이다.
출력
얻을 수 있는 친구 수의 최댓값을 하나의 정수로 출력한다.