시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 3 0 0 0.000%

문제

It is necessary to produce legislative framework document, just to be able to organize an important event. To be entered into force, this document must be signed by N officials, and the order in which officials sign the document is fixed. We assume that officials are numbered in the order of signing, starting from the official number 1, and ending with official number N. 

It is known that every official accept documents only at fixed set of days of weeks (visiting days). Also, despite the week has seven days, officials accept documents only on the working days (Monday to Friday). Every official has at least one visiting day within week. 

One official needs exactly one day to sign the document, i.e. if an official reviews the document at some day, other officials can not review this document that day. 

Some Monday morning you get a document to be signed (let us count this day as the first day). Write a program which will calculate the minimum number of days required to get all signs for this document in the specified order. If the document can not be completed within one week, you can continue to sign it next week, and so on. 

It is guaranteed that the document is very well prepared and any official will sign it at the first submit within one day, without any claims. 

입력

First line of input file contains N — the number of officials (1 ≤ N ≤ 50). The following N lines contain five space-separated integers each, corresponding to the days of week from Monday to Friday, inclusive. The number in i-th row, corresponding to j-th day of week, is equal to 0, if i-th official doesn’t accept documents at j-th day of week, otherwise it equals 1. 

 

출력

Output file contains one integer — the minimal number of days required to sign the document. 

 

예제 입력

2
1 0 1 0 1
1 0 0 1 0

예제 출력

4

예제 입력 2

2
0 1 0 0 1
1 1 0 0 0

예제 출력 2

8

힌트

In the first example, the document must be signed by two officials — the first one accept documents on Mondays, Wednesdays and Fridays, and the second one — on Mondays and Thursdays. The fastest way to sign the document is one of the following: you submit the document to the first official on Monday or on Wednesday, and then submit it to the second official on Thursday, so you will need 4 days to sign document. In the second example, the first official works on Tuesdays and Fridays, and the second one — on Mondays and Tuesdays. Even if you submit the document to the first official on Tuesday, you will not complete the process within first week, you can only do this on the next Monday, and the whole process will take 8 days.