로켓 단

많은 로켓은 효율을 높이기 위해 여러 개의 단(段)으로 이루어집니다. 한 단의 연료가 다 타면 그 단을 분리해 버릴 수 있으며, 그러면 남은 로켓의 무게가 줄어듭니다. 첫 번째 단은 로켓 전체를 들어 올릴 수 있는 강력한 엔진이 필요하지만, 나중 단들은 더 작은 엔진을 써도 됩니다.

이 문제에서는 모든 연료가 다 탔을 때 로켓의 위쪽 속도가 최대가 되도록 어떤 단들을 결합할지 정해야 합니다.

각 단은 다음 네 값으로 주어집니다.

• 연료가 없을 때의 빈 질량 $S$ (킬로그램),
• 그 단에 실린 연료의 질량 $L$ (킬로그램),
• 엔진이 내는 추력 $T$ (뉴턴),
• 그 단의 연료 소모율 $C$ (초당 킬로그램).

로켓은 비행 내내 똑바로 위를 향한다고 가정합니다. 로켓에는 두 힘이 작용합니다. 하나는 위쪽으로 $T$ 뉴턴인 엔진의 힘이고, 다른 하나는 아래쪽으로 $9.8M$ 뉴턴인 중력입니다. 여기서 $M$은 연료를 포함한 로켓의 현재 총 질량(킬로그램)입니다. 로켓의 가속도는 위쪽으로 $F/M$ (미터 매 초 제곱)이며, $F$는 로켓에 작용하는 알짜힘(뉴턴), $M$은 현재 총 질량입니다. 한 단이 다 타는 즉시 그 단은 분리되고 다음 단이 타기 시작합니다. 로켓의 최종 속도는 알짜 가속도를 시간에 대해 적분한 값입니다.

안전 규정상, 로켓의 연료가 다 떨어지기 전까지 알짜 가속도가 아래쪽을 향해서는 안 됩니다. 또한 안전 규정상, 로켓의 총 질량은 $10000$ 킬로그램을 넘을 수 없습니다. 로켓은 적어도 하나의 단을 가져야 합니다.

첫째 줄에 테스트 케이스의 개수를 나타내는 정수 하나가 주어집니다.

각 테스트 케이스의 첫 줄에는 사용할 수 있는 단의 개수 $N$이 주어집니다($N \le 1000$). 이어지는 $N$개의 줄에는 각각 위에서 설명한 대로 한 단을 나타내는 네 정수 $S$, $L$, $T$, $C$가 주어집니다. 각 정수는 32비트 부호 없는 값으로 나타낼 수 있습니다. 단들의 주어진 순서는 반드시 유지해야 하지만, 그중 일부는 (첫 번째 단을 포함해) 로켓에서 뺄 수 있습니다. 가장 먼저 나열된 단이 로켓의 맨 위에 있으며, 따라서 가장 나중에 탑니다. 모든 테스트 케이스에서 문제의 조건을 모두 만족하는 로켓을 적어도 하나는 만들 수 있음이 보장됩니다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력합니다. 이는 로켓이 연소를 마쳤을 때 낼 수 있는 최대 속도(미터 매 초)를 가장 가까운 정수(미터 매 초)로 반올림한 값입니다.