문제
정수의 연속된 닫힌구간을 나타내는 ai, bi와 정수 ci가 N개 주어질 때 아래와 같은 프로그램을 작성하시오.
ai, bi, ci가 주어질 때 의미하는 것은 ai이상 bi이하 정수 중에 적어도 ci개의 정수를 포함하는 정수 집합을 만들어야 함을 말한다. N개의 정보가 주어질 때 N개 모두 만족하는 정수 집합 중에서 원소의 개수가 최소인 경우 원소의 개수를 구하는 프로그램을 작성하시오.
예를 들어 아래와 같이 다섯 개의 데이터가 주어졌다고 하자.
3 7 3 -> 3, 4, 5, 6, 7중에 적어도 3개의 수를 포함시켜야 한다는 의미 8 10 3 6 8 1 1 3 1 10 11 1
이때 가능한 정수 집합은 {3, 4, 5, 8, 9, 10}, {3, 5, 6, 7, 8, 9, 10}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, }등이 있으나 원소의 개수가 가장 작은 경우는 6인 경우이다.
입력
첫 행에 정보의 개수 N ( 1 ≤ N ≤ 50,000)이 입력된다.
다음 N개의 행에 정보를 나타내는 ai, bi, ci ( 0 ≤ ai ≤ bi ≤ 50,000 1 ≤ ci ≤ bi - ai +1)이 공백으로 구분되어 입력된다.
출력
조건을 만족하는 정수 집합 중에서 최소 원소를 갖는 정수 집합의 원소의 개수를 출력한다.
예제
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
6
출처
Southwestern Europe 2002
로그인해야 코드를 작성할 수 있어요.