1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
import sys
from fractions import Fraction

def main():
    n, L = map(int, sys.stdin.readline().split())
    schedules = [sys.stdin.readline().strip() for _ in range(n)]
    
    available = []
    for s in schedules:
        intervals = []
        start = None
        for i in range(L):
            if s[i] == '.':
                if start is None:
                    start = i
            else:
                if start is not None:
                    intervals.append((start, i))
                    start = None
        if start is not None:
            intervals.append((start, L))
        available.append(intervals)
    
    all_available = []
    for intervals in available:
        for a, b in intervals:
            all_available.extend([(a, True), (b, False)])
    all_available.sort(key=lambda x: (x[0], not x[1]))
    
    coverage = 0
    cnt = 0
    last = 0
    total_cover = True
    for pos, is_start in all_available:
        if cnt == 0 and is_start:
            if pos > last:
                total_cover = False
                break
            last = pos
        if is_start:
            cnt += 1
        else:
            cnt -= 1
            if cnt == 0:
                coverage += pos - last
                last = pos
    if last < L:
        total_cover = False
    if not total_cover:
        print(-1)
        return
    
    max_T_per = []
    for intervals in available:
        max_len = 0
        for a, b in intervals:
            max_len = max(max_len, b - a)
        max_T_per.append(max_len)
    min_max_T = min(max_T_per)
    if min_max_T == 0:
        print("0/1")
        return
    
    def is_possible(T):
        earliest = []
        latest = []
        for intervals in available:
            earliest_start = None
            latest_start = None
            for a, b in intervals:
                if b - a >= T:
                    if earliest_start is None:
                        earliest_start = a
                    candidate = b - T
                    if latest_start is None or candidate > latest_start:
                        latest_start = candidate
            if earliest_start is None:
                return False
            earliest.append(earliest_start)
            latest.append(latest_start)
        
        from itertools import product
        for choices in product([0, 1], repeat=n):
            awake = []
            for i in range(n):
                s = earliest[i] if choices[i] else latest[i]
                e = s + T
                for a, b in available[i]:
                    if b <= s or a >= e:
                        awake.append((a, b))
                    else:
                        if a < s:
                            awake.append((a, s))
                        if e < b:
                            awake.append((e, b))
            awake.sort()
            merged = []
            for a, b in awake:
                if merged and merged[-1][1] >= a:
                    merged[-1] = (merged[-1][0], max(merged[-1][1], b))
                else:
                    merged.append((a, b))
            if not merged:
                continue
            if merged[0][0] > 0:
                continue
            if merged[-1][1] < L:
                continue
            prev = 0
            valid = True
            for a, b in merged:
                if a > prev:
                    valid = False
                    break
                prev = b
            if valid and prev >= L:
                return True
        return False
    
    left = 0.0
    right = min_max_T
    best_num = 0
    best_den = 1
    eps = 1e-9
    for _ in range(100):
        mid = (left + right) / 2
        if is_possible(mid):
            best_num = mid
            best_den = 1
            left = mid
        else:
            right = mid
    
    numerator = 0
    denominator = 1
    for den in range(1, 101):
        for num in range(0, den * int(min_max_T) + 1):
            T = Fraction(num, den)
            if T.numerator == num and T.denominator == den and is_possible(T):
                if T > Fraction(numerator, denominator):
                    numerator = T.numerator
                    denominator = T.denominator
    print(f"{numerator}/{denominator}")

if __name__ == "__main__":
    main()