Maximizing Fair Sleep Time

There are n people and a time period [0, l) divided into l unit intervals [0,1), [1,2), …, [l-1,l). For each person i (1 ≤ i ≤ n) and each unit interval [j, j+1) (0 ≤ j ≤ l-1), you are given whether the person is free during that time (represented by 1 for free and 0 for busy).

If a person is free during a time interval, they may choose to either take care of the baby or sleep during that interval. In the time period [0,l), each person may sleep at most once (i.e. they may have at most one contiguous sleep period) and then wake up once. For fairness, if anyone sleeps then every person’s sleep duration must be exactly t (with t \ge 0). A person is allowed to sleep in an interval [a, a+t) if and only if:

• a+t \le l, and
• the person is free during the entire interval [a, a+t).

The baby must be cared for at every moment. In other words, for every time x \in [0,l) there must be at least one person who is free and awake at time x.

Your task is to help arrange each person’s sleep schedule (each person must either sleep for time t in some free slot or, if not possible, remain awake) so as to maximize the common sleep duration t while satisfying the above coverage constraint. It can be proved that if a positive t is achievable then the maximum t is a rational number. Output this maximum value in the form of an irreducible fraction.

Note: Time is discretized into unit intervals. For each person, the free time is given as a binary string of length l. A person may have several contiguous free segments. If a person sleeps in one segment then he is forced to lose some part of that segment (either at the beginning or at the end) according to his chosen sleep option. In the other free segments (in which he does not sleep) he is entirely awake. All these awake periods contribute to baby care. The sleep scheduling must be done in such a way that, for every unit interval [j, j+1), at least one person who is free during that interval is awake.

Formally, if a person chooses to sleep in a free segment [p,q) then:

• if the person sleeps at the beginning (i.e. starting at p), the sleep interval is [p, p+t) and he is awake in that segment during [p+t, q) (covering those unit intervals [j,j+1) for which j+1 \gt p+t),
• if he sleeps at the end (i.e. finishing at q), he sleeps in [q-t, q) and is awake in [p, q-t).

Determine the maximum t (in irreducible fraction form) for which a valid sleep schedule exists for all people.

inputFormat

The first line contains two integers n and l (1 ≤ n ≤ 10, 1 ≤ l ≤ 50), representing the number of people and the length of the time period respectively. Each of the next n lines contains a binary string of length l. The j-th character (0-indexed) in the i-th string is '1' if person i is free during time interval [j, j+1); otherwise, it is '0'.

You may assume that at every time x in [0,l) there is at least one person who is free.

outputFormat

Output the maximum value of t as an irreducible fraction in the format p/q (without quotes), where p and q are integers and the fraction is in lowest terms. If no positive t is achievable, output 0/1.

sample

3 5
11111
10111
11101

1/1