상수도관 파열

상수도관이 파열되면 수리될 때까지 한동안 물이 새어 나온다. 이 문제에서는 여러 건의 상수도관 파열에 대한 정보, 즉 각 파열이 시작된 시각, 끝난 시각, 그리고 물이 새어 나온 속도가 주어지며, 함께 하나의 시간 구간이 주어진다. 주어진 구간 동안 낭비된 물의 총량을 계산하는 것이 목표이다.

시간은 정수 초 단위로 측정한다. 시작 시각이 si이고 종료 시각이 fi인 파열은 각 초 si, si+1, ..., fi(양쪽 끝 포함)마다 ri 갤런의 물을 흘려보내며, fi + 1초부터는 수리된 것으로 본다.

첫째 줄에 데이터 세트의 개수 K가 주어진다. 각 데이터 세트는 다음과 같은 형식이다.

• 첫째 줄에 정수 n (0 ≤ n ≤ 30), 즉 상수도관 파열의 개수가 주어진다.
• 둘째 줄에 두 정수 s와 f (0 ≤ s ≤ f ≤ 1000)가 주어진다. 이는 낭비된 물을 계산할 구간 [s, f]의 시작 초와 끝 초이다.
• 이어지는 n개의 줄에는 각 파열을 나타내는 세 정수 si, fi, ri (0 ≤ si ≤ fi ≤ 1000, 0 ≤ ri ≤ 1000)가 주어진다. 각각 파열의 시작 초, 끝 초, 그리고 초당 갤런 단위의 유출 속도이다.

각 데이터 세트마다 먼저 Data Set x: 형태의 줄을 출력한다. 여기서 x는 1부터 시작하는 데이터 세트의 번호이다. 그 다음 줄에는 구간 [s, f] 동안 낭비된 물의 총 갤런 수를 출력한다. 이는 각 초 s, s+1, ..., f에 새어 나온 물을 모두 합한 값이다. 연속한 데이터 세트의 출력 사이에는 빈 줄 하나를 넣어 구분한다.