2330번 - 미생물 연구실

초라기 연구소에서는 N종류의 미생물을 이용한 실험을 하고 있다. 주된 실험 내용은 같은 미생물을 여러 다른 온도에서 길러 보면서 각각 어떤 모습으로 자라는지 관찰하는 것이다.

i번째 미생물(편의상 미생물에 1부터 N까지의 번호를 붙이자)은 A[i]이상 B[i]이하의 온도에서만 기를 수 있다. 또, 원활한 실험을 위해서는 최소한 C[i]개의 서로 다른 온도의 실험실에서 i번째 미생물을 길러봐야 한다. 이와 같은 조건이 주어졌을 때, 필요한 실험실의 최소 개수를 구하는 프로그램을 작성하시오.

각각의 실험실은 어떤 특정한, 그리고 서로 다른 온도로 관리된다. 어떤 실험실의 온도가 T도일 때, A[i] ≤ T ≤ B[i]를 만족하는 미생물은 몇 개라도, 몇 종류라도 그 실험실에서 기를 수 있다고 하자. 또한 월드 연구소에서는 특별한 단위의 온도를 사용하는데, A[i], B[i], T등 모든 온도가 0이상 50,000 이하의 정수로 표현되는 단위를 사용한다.

첫째 줄에 N이 주어진다. 다음 N개의 줄에는 A[i], B[i], C[i]가 i = 1, 2, ..., N의 순서로 주어진다.

첫째 줄에 필요한 최소 개수의 실험실을 출력한다.

• 1 ≤ N ≤ 50,000
• 0 ≤ A[i] ≤ B[i] ≤ 50,000
• 1 ≤ C[i] ≤ B[i] - A[i] + 1

온도가 1인 실험실, 3인 실험실 두 개가 있으면 된다.