에너지 돌

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

Duda는 에너지 돌을 먹어서 에너지를 얻는다. 돌마다 주는 에너지의 양이 다르다. 게다가 돌은 시간이 지나면서 에너지를 잃는다. i번째 돌은 처음에 Ei만큼의 에너지를 가지고 있으며 매초 Li만큼의 에너지를 잃는다. Duda가 돌을 먹기 시작하면, 그 돌을 실제로 다 먹는 데 걸리는 시간과 상관없이 즉시 돌이 가지고 있는 에너지를 모두 받는다. 돌의 에너지는 0이 되면 더 이상 줄지 않는다.

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

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스의 첫 줄에는 Duda가 가진 에너지 돌의 수인 정수 N이 주어진다. 그다음 N개의 줄이 주어지며, i번째 줄에는 위에서 설명한 세 정수 Si, Ei, Li가 주어진다.

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

• 1 ≤ T ≤ 100.
• 1 ≤ N ≤ 100.
• 1 ≤ Si ≤ 100.
• 1 ≤ Ei ≤ 105.
• 0 ≤ Li ≤ 105.