C. Fat Burner II
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After successfully tackling the rest and work balance last week, now you want to know exactly which exercises you must do on a particular training plan to burn the most fat.

You also have been browsing the internet, so you are learning about new exercises. So each day you are learning about some exercises. Here is how u can use them.

If you learn about a new exercise on day $$$i$$$, you can use it once to burn fat anytime between day $$$i$$$ and $$$n$$$

Also some exercises might make u gain fat instead of losing fat, they are identified by a negative fat burn.

You have n working days ahead of you, and your goal is to burn the most amount of fat after all n working days. Each day u need to choose atmost one exercise to perform. To balance the workload, you can perform an exercise only once throughout the n days.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 50$$$) — the number of testcases

  • The first line contains a single integer, $$$n$$$ ($$$1 \leq n \leq 100$$$), the number of days
  • Then follow $$$n$$$ lines, each line first has an integer $$$k$$$, followed by $$$k$$$ integers, the fat burned by the exercises you have learned on day $$$i$$$. ($$$0 \leq k \leq 10^5$$$), ($$$-10^9 \leq fat \leq 10^9$$$)

It is guaranteed that sum of $$$k$$$ over all days does not exceed $$$10^5$$$

Output

For each test, print the maximum fat u can burn

Example
Input
1
5
2 5 10
2 9 4
2 11 3
2 20 1
1 35
Output
85