Problem: The volume of access to a web service varies from time to time in a day. Also, the hours with the highest volume of access varies from service to service. For example, a service popular in the United States may receive more access in the daytime in the United States, while another service popular in Japan may receive more access in the daytime in Japan. When you develop a web service, you have to design the system so it can handle all requests made during the busiest hours.

You are a lead engineer in charge of a web service in the 30th century. It’s the era of Galaxy Wide Web (GWW), thanks to the invention of faster-than-light communication. The service can be accessed from all over the galaxy. Thus many intelligent creatures, not limited to human beings, can use the service. Since the volume of access to your service is increasing these days, you have decided to reinforce the server system. You want to design a new system that handles requests well even during the hours with the highest volume of access. However, this is not a trivial task. Residents in each planet have their specific length of a day, say, a cycle of life. The length of a day is not always 24 hours. Therefore, a cycle of the volume of access are different by planets of users.

You have obtained hourly data of the volume of access for all planets where you provide the service. Assuming the volume of access follows a daily cycle for each planet, you want to know the highest volume of access in one hour. It should be a quite easy task for you, a famous talented engineer in the galaxy.



Input

The input consists of multiple datasets. Each dataset has the following format:

N
d1 t1 q1,0 ... q1,d1-1
...
dN tN qN,0 ... qN,dN-1


N is the number of planets. di (1 ≤ i ≤ N) is the length of a day in the planet i.  ti (0 ≤ ti ≤ di - 1) is the current time of the planet i. qi, j is the volume of access on the planet i during from the j-th hour to the (j+1)-th hour.

You may assume that N ≤ 100, di ≤ 24, qi, j ≤ 1000000 (1 ≤ i ≤ N, 0 ≤ j ≤ di - 1).

The last dataset is followed by a line containing one zero. This line is not a part of any dataset and should not be processed.

Output

For each dataset, output the maximum volume of access in one hour in a line.

Example

Input

2
4 0 1 2 3 4
2 0 2 1
0


Output

5

Solution (in CPP):

Solution:
#include "bits/stdc++.h"
using namespace std;

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2017/11/15  Problem: AOJ 2162 / Link: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2162  ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----

全周期をみたいけどLCM(1 to 24)は5*10^9overなのできびしい。
3,7だけ見ると愚直をしなくての3maxと7maxをとって足しても答えになる。これは互いに素の時のみできる
つまり2,4は無理
互いに素なものは別でやっていいのでなるべく取り除けばLCMを小さくできる。
今回はmaxが24なので13以上の素数を取り除くと、これらのLDMは 55440でハッピー
こっちは全探索をしてあとは独立にやってもよいから間に合ってくれる。

----解説ここまで---- */

LL N;

LL ans = 0LL;
bool doku(int a) { return (a == 13 || a == 17 || a == 19 || a == 23); }

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	map<int, int>m;
	while (cin >> N, N) {
		VL a(55440 + 1, 0);
		VVL b(24 + 1, VL(24, 0));
		FOR(_, 0, N) {
			int d; cin >> d;
			int t; cin >> t;
			VL in(d);
			FOR(j, 0, d) {
				cin >> in[j];
				b[d][(j - t + d) % d] += in[j];
			}
		}
		ans = 0;
		FOR(i, 1, 24 + 1) {
			if (doku(i)) {
				ans += *max_element(ALL(b[i]));
			}
			else {
				FOR(j, 0, 55440 + 1) {
					a[j] += b[i][j%i];
				}
			}
		}
		ans += *max_element(ALL(a));
		cout << ans << endl;
	}
	return 0;

}