에너지 돌

바위 괴물 Duda는 마법의 숲에 살며 점심으로 먹을 N개의 에너지 돌을 모았다. 입이 작기 때문에 에너지 돌을 한 번에 하나씩 먹는다. 어떤 돌은 다른 돌보다 더 단단하다! i번째 돌을 먹는 데 $S_{i}$초가 걸린다.

Duda는 에너지를 얻기 위해 에너지 돌을 먹는다. 돌마다 그에게 주는 에너지의 양이 다르다. 또한 돌은 시간이 지남에 따라 에너지를 잃는다. i번째 돌에는 처음에 $E_{i}$단위의 에너지가 들어 있으며, 매초 $L_{i}$단위의 에너지를 잃는다. Duda가 돌을 먹기 시작하면, 실제로 그 돌을 다 먹는 데 시간이 얼마나 걸리는지와 관계없이 그 돌에 들어 있는 모든 에너지를 즉시 받는다. 돌의 에너지는 영에 도달하면 더 이상 감소하지 않는다.

Duda가 자신의 돌을 먹어서 받을 수 있는 에너지의 최대량은 얼마인가?

제한

테스트 세트당 시간 제한: 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 1 ≤ N ≤ 100. 1 ≤ $S_{i}$ ≤ 100. 1 ≤ $E_{i}$ ≤ $10^{5}$. 0 ≤ $L_{i}$ ≤ $10^{5}$.

테스트 세트 1 (공개)

모든 돌을 먹는 데 같은 시간이 걸린다. 즉, 모든 i와 j에 대해 $S_{i}$ = $S_{j}$이다.

테스트 세트 2 (비공개)

일반 제한 외에 추가 제약 조건은 없다.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 Duda가 가진 에너지 돌의 수를 나타내는 정수 N이 담긴 줄로 시작한다. 그다음 N개의 줄이 더 주어지며, 그중 i번째 줄에는 위에서 설명한 세 정수 $S_{i}$, $E_{i}$, $L_{i}$가 주어진다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y은 Duda가 돌을 먹어서 받을 수 있는 에너지의 최대량이다.

예제 케이스 #1에는 N = 3개의 돌이 있다. Duda가 어떤 돌을 먹더라도, 그 돌을 다 먹을 때쯤이면 나머지 두 돌에는 에너지가 남아 있지 않게 된다. 따라서 세 번째 돌을 먹어 8단위의 에너지를 얻어야 한다.

추가 예제 - 테스트 세트 2

예제 케이스 #1에는 N = 4개의 돌이 있다. Duda가 돌을 먹을 수 있는 순서 중 하나는 다음과 같다.

• 네 번째 돌을 먹는다. 여기에는 5초가 걸리고, 80단위의 에너지를 얻는다.

• 두 번째 돌을 먹는다. 여기에는 추가로 5초가 걸리고, 5단위의 에너지를 얻는다(두 번째 돌은 처음에 30의 에너지를 가지고 있었고, 5초 동안 25단위의 에너지를 잃었다).

• 세 번째 돌을 먹는다. 여기에는 추가로 100초가 걸리고, 20단위의 에너지를 얻는다(세 번째 돌은 처음에 30의 에너지를 가지고 있었고, 10초 동안 10단위의 에너지를 잃었다).

• 첫 번째 돌을 먹는다. 여기에는 추가로 20초가 걸리고, 0단위의 에너지를 얻는다(첫 번째 돌은 처음에 10단위의 에너지를 가지고 있었고, 110초 동안 에너지를 모두 잃었다).

이렇게 하면 105단위의 에너지를 얻으며, 이것이 얻을 수 있는 최대량이다. 따라서 정답은 105이다.

예제 케이스 #2에는 N = 2개의 돌이 있다. Duda는 다음과 같이 할 수 있다.

• 첫 번째 돌을 먹는다. 여기에는 12초가 걸리고, 300단위의 에너지를 얻는다.

• 두 번째 돌을 먹는다. 여기에는 5초가 걸리고, 200단위의 에너지를 얻는다(두 번째 돌은 시간이 지나도 에너지를 전혀 잃지 않는다!).

따라서 정답은 500이다.