만리장성

당신은 북쪽의 군사적 침입을 막기 위해 중국인들이 건설한 만리장성의 역사를 연구하고 있다. 이 문제에서 만리장성은 동쪽의 무한대부터 서쪽의 음의 무한대까지 뻗어 있다. 이는 한꺼번에 건설하기에는 매우 긴 거리이므로, 만리장성은 한 번에 건설되지 않았다. 대신 이 문제에서는 건설자가 대응적인 전략을 사용했다고 가정한다. 국경의 어떤 부분이 공격을 받아 돌파될 때마다, 국경의 해당 부분에 있는 장벽을 미래에 동일한 공격을 막기에 충분한 높이까지 높였다.

중국의 북쪽 국경은 유목 부족들의 공격을 자주 받았다. 이 문제에서는 각 부족이 어떤 구간의 국경을 어떤 세기 S로 공격한다고 가정한다. 공격을 격퇴하려면 방어하는 구간 전체에서 장벽의 높이가 S여야 한다. 장벽의 아주 짧은 부분이라도 필요한 높이보다 낮으면 공격은 그 지점에서 장벽을 돌파하여 성공한다. 공격이 성공하더라도 장벽은 손상되지 않는다는 점에 유의한다. 공격 후에는 공격받은 장벽의 모든 부분 중 높이가 S보다 낮았던 부분을 높이 S까지 높인다. 즉, 해당 공격을 막을 수 있었을 최소한의 방식으로 장벽을 높인다. 둘 이상의 공격이 정확히 같은 날에 일어났다면, 모든 공격의 결과가 정해진 후에야 장벽을 높이며, 그 공격들을 모두 막을 수 있었을 최소한의 방식으로 높인다는 점에 유의한다.

유목 부족들은 유목 생활을 했으므로 반드시 한 번의 공격에만 그치지는 않았다. 대신 이들은 동쪽이나 서쪽으로 이동하면서 주기적으로 장벽을 공격하는 경향이 있었다. 문제를 단순화하기 위해, 이들이 일정한 속도로 이동하고 일정한 간격으로 장벽을 공격했다고 가정한다. 또한 특정 부족이 장벽을 공격하는 세기는 각 공격 후에 일정한 양만큼 변했다고 가정한다. 소모로 인해 감소하기도 했고, 경험으로 인해 증가하기도 했다.

초기에(250 BC) 장벽이 존재하지 않았다고, 즉 모든 곳에서 높이가 영이었다고 가정하자. 장벽을 공격한 모든 유목 부족에 대한 완전한 설명이 주어질 때, 성공한 공격의 수를 구한다.

제한

시간 제한: 테스트 세트당 60초. 메모리 제한: 1GB. 1 ≤ T ≤ 20. 0 ≤ $d_{i}$. 1 ≤ delta_d_{i} ≤ 676060. $d_{i}$ + ($n_{i}$ - 1) * delta_d_{i} ≤ 676060. 1 ≤ $s_{i}$ ≤ $10^{6}$. -$10^{5}$ ≤ delta_s_{i} ≤ $10^{5}$. $s_{i}$ + ($n_{i}$ - 1) * delta_s_{i} ≥ 1.

작은 데이터 세트(테스트 세트 1 - 공개)

1 ≤ N ≤ 10. 1 ≤ $n_{i}$ ≤ 10. -100 ≤ $w_{i}$ < $e_{i}$ ≤ 100. -10 ≤ delta_p_{i} ≤ 10.

큰 데이터 세트(테스트 세트 2 - 비공개)

1 ≤ N ≤ 1000. 1 ≤ $n_{i}$ ≤ 1000. -$10^{6}$ ≤ $w_{i}$ < $e_{i}$ ≤ $10^{6}$. -$10^{5}$ ≤ delta_p_{i} ≤ $10^{5}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 장벽을 공격하는 부족의 수를 나타내는 하나의 정수 N이 담긴 줄로 시작한다. 이어지는 N개의 줄은 각각 하나의 부족을 설명한다. i번째 줄에는 하나의 유목 부족을 설명하는 여덟 정수 $d_{i}$, $n_{i}$, $w_{i}$, $e_{i}$, $s_{i}$, delta_d_{i}, delta_p_{i}, 그리고 delta_s_{i}가 공백으로 구분되어 주어진다.

• $d_{i}$ – 해당 부족이 처음 공격한 날(기원전 250BC년 1st January를 0일로 간주한다)

• $n_{i}$ – 해당 부족이 감행한 공격의 수

• $w_{i}$, $e_{i}$ – 각각 첫 공격에서 공격한 장벽 구간의 가장 서쪽 지점과 가장 동쪽 지점

• $s_{i}$ – 첫 공격의 세기

• delta_d_{i} – 해당 부족의 연속한 두 공격 사이의 일수

• delta_p_{i} – 해당 부족이 연속한 두 공격 사이에 동쪽으로 이동하는 거리(이 값이 음수이면 부족은 서쪽으로 이동한다)

• delta_s_{i} – 연속한 두 공격 사이의 세기 변화량

각 테스트 케이스마다 "Case #x: y"를 담은 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 성공한 공격의 수이다.

첫 번째 케이스에서 첫 번째 부족은 세 번 공격한다. 0일에는 높이 10로 구간 $[0,2]$을 공격하고, 2일에는 높이 8로 $[3,5]$을 공격하며, 4일에는 높이 6로 $[6,8]$을 공격한다. 세 공격 모두 성공한다. 그다음 두 번째 부족이 매번 높이 8로 세 번 공격한다. 10일에는 $[2,3]$을 공격한다. 이 공격은 성공하는데, 예를 들어 위치 2.5에서 장벽의 높이는 여전히 0이다. 17일에는 $[4,5]$을 공격한다. 이 공격은 실패하는데, $[4, 5]$을 포함하는 구간 $[3, 5]$에서 장벽의 높이가 이미 8이기 때문이다. 24일에는 $[6,7]$을 공격한다. 그곳의 장벽 높이가 6이었으므로 이 공격은 성공한다.

두 번째 케이스에는 세 부족이 있으며, 이들의 공격은 서로 뒤섞여 일어난다. 순서는 다음과 같다.

• 0일에 부족 2이 높이 7로 $[0,1]$을 공격하여 성공한다.

• 1일에 부족 1이 높이 10로 $[0,5]$을 공격하고, 부족 2이 높이 9로 $[2,3]$을 공격한다. 두 공격 모두 성공한다. 두 공격이 동시에 일어났으므로 첫 번째 부족의 공격 후에 건설된 장벽은 두 번째 부족을 막을 수 있을 만큼 일찍 존재하지 않기 때문이다.

• 2일에 부족 2이 높이 11로 $[4,5]$을 공격하여 성공한다. 그곳의 장벽 높이는 10이었다.

• 3일에 부족 1이 높이 10로 $[8,13]$을 공격하여 성공한다. 동시에 부족 3이 높이 1로 $[0,5]$을 공격하여 실패한다. 그곳에는 높이가 10와 11인 장벽이 있기 때문이다.

• 4일에 부족 3이 높이 1로 $[4,9]$을 공격하여 성공한다. 5과 8 사이에는 장벽이 없었다.

• 마지막으로 5일에 부족 3이 높이 1로 $[8,13]$을 공격하여 실패한다. 그곳에 높이 10인 장벽이 있기 때문이다.