수영장 안전요원 (플래티넘)
시간 제한2초메모리 제한512 MB
N개의 근무 구간 중 정확히 K개를 해고해 남은 구간이 하나 이상 덮는 시간의 합이 최대가 되도록 한다.
문제
존 농부는 젖소가 쉬면서 우유를 더 많이 내도록 수영장을 열었다.
안전을 위해 젖소 마리를 안전요원으로 고용했다. 안전요원은 저마다 하루 중 연속된 구간 하나를 근무한다. 수영장은 매일 시각 부터 시각 까지 열려 있으므로, 근무 구간은 근무를 시작하는 시각과 끝내는 시각, 정수 두 개로 나타낸다. 예를 들어 시각 에 시작해 시각 에 끝나는 안전요원은 시간 3단위를 감시한다. 시각은 길이가 없는 한 점이다.
존 농부가 고용한 안전요원은 급여를 감당할 수 있는 수보다 마리 많다. 그래서 정확히 마리를 해고해야 한다. 남은 안전요원 중 적어도 한 마리가 근무하는 시간은 감시된다. 해고한 뒤 남은 근무 구간이 감시할 수 있는 시간의 최댓값을 구하여라.
입력
첫째 줄에 과 가 주어진다 (, ).
다음 개 줄에는 안전요원 한 마리의 근무 시작 시각과 끝 시각이 이상 이하의 정수로 주어진다. 시작 시각은 끝 시각보다 작다. 입력에 나오는 시각 개는 모두 서로 다르다. 서로 다른 안전요원의 근무 구간은 겹치기도 한다.
출력
정확히 마리를 해고한 뒤 감시할 수 있는 시간의 최댓값을 한 줄에 출력한다.
힌트
첫 번째 예제에서는 부터 까지 근무하는 안전요원과 부터 까지 근무하는 안전요원을 해고하면 된다. 남은 근무 구간 부터 까지가 시간 12단위를 감시한다.