Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import math

A,B=map(int, input().split())

def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def primelist(n):
    P = [2]
    flag = 0
    for i in range(3,n+1,2):
        for j in range(len(P)):
            if math.sqrt(i) < P[j]:
                break
            else:
                if i%P[j] == 0:
                    flag += 1
                    break
        if flag == 0:
            P.append(i)
        flag = 0
    P.append(1)
    return(P)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr[-1][0]

N=gcd(A,B)

if N==1:
    print(1)
else:
    ms = factorization(N)
    pl = primelist(ms)
    ans=0
    for i in range(len(pl)):
        if N%pl[i]==0:
            ans+=1
    print(ans)

### FIXED CODE ###

import collections

def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

A,B=map(int, input().split())
N=gcd(A,B)
c = collections.Counter(prime_factorize(N))
print(len(list(c.keys()))+1)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A1 = [[-a-i,i] for i, a in enumerate(A)]
A2 = [[a-i,i] for i, a in enumerate(A)]
A1.sort()
A2.sort()
i = j = 0
cnt = 0
while i < N and j < N:
    if A1[i][0] == A2[j][0]:
        buf1 = 1
        for k in range(i+1, N):
            if A1[k][0] != A1[i][0]:
                break
            buf1 += 1
        buf2 = 1
        for k in range(j+1, N):
            if A2[k][0] != A2[j][0]:
                break
            buf2 += 1
        for i_ in range(i, i+buf1):
            for j_ in range(j, j+buf2):
                if A1[i_][1] < A2[j_][1]:
                    cnt += 1
        i += buf1
        j += buf2
    elif A1[i][0] < A2[j][0]:
        i += 1
    else:
        j += 1
print(cnt)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A1 = [[-a-i,i] for i, a in enumerate(A)]
A2 = [[a-i,i] for i, a in enumerate(A)]
A1.sort()
A2.sort()
i = j = 0
cnt = 0
while i < N and j < N:
    if A1[i][0] == A2[j][0]:
        buf1 = 1
        for k in range(i+1, N):
            if A1[k][0] != A1[i][0]:
                break
            buf1 += 1
        buf2 = 1
        for k in range(j+1, N):
            if A2[k][0] != A2[j][0]:
                break
            buf2 += 1
        cnt += buf1 * buf2
        i += buf1
        j += buf2
    elif A1[i][0] < A2[j][0]:
        i += 1
    else:
        j += 1
print(cnt)
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
A = [0, 1.0]
for i in range(2, 1001):
    A.append(A[i-1]+0.5)
index = 0
tmp = 0
for i in range(0, N-K+1):
    total = sum(P[i:i+K])
    if tmp < total:
        index = i
        tmp = total
ans = 0
for i in range(index, index+K):
    ans += A[P[i]]
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
A = [0, 1.0]
for i in range(2, 1001):
    A.append(A[i-1]+0.5)
index = 0
tmp = sum(P[0:K])
B = [tmp]
for i in range(K, N):
    total = B[-1]-P[i-K]+P[i]
    if tmp < total:
        index = i-K+1
        tmp = total
    B.append(total)
ans = 0
for i in range(index, index+K):
    ans += A[P[i]]
print(ans)
### BUGGY CODE ###

n = int(input())
A = sorted(((v, i) for i, v in enumerate(map(int, input().split()))))

ans = 0
for i in range(n):
    for j in range(i, n):
        hi, ki = A[i]
        hj, kj = A[j]
        if abs(kj - ki) == hi + hj:
            ans += 1
        if hi >= n:
            break
print(ans)


### FIXED CODE ###

from collections import defaultdict


n = int(input())
A = map(int, input().split())

L = defaultdict(int)
R = defaultdict(int)
for i, v in enumerate(A):
    L[i + v] += 1
    R[i - v] += 1
print(sum(L.get(i, 0) * R.get(i, 0) for i in range(n)))
### BUGGY CODE ###

def gud(a,b):
  if a%b==0:
    return b
  else:
    return gud(b,a%b)
a=int(input())
ans=0
for i in range(a):
  for j in range(a):
    for k in range(a):
      n=gud(i+1,j+1)
      ans+=gud(n,k+1)
print(ans)

### FIXED CODE ###

import math
def gud(a,b):
  if a%b==0:
    return b
  else:
    return gud(b,a%b)
a=int(input())
ans=0
for i in range(1,a+1):
  for j in range(1,a+1):
    n=math.gcd(i,j)
    for k in range(1,a+1):
      ans+=math.gcd(n,k)
print(ans)
### BUGGY CODE ###

def main():
    n=int(input())
    if n==1:
        print("Yes")
        print(2)
        print(1,1)
        print(1,1)
        exit()
    a=1
    while True:
        t=a*(a-1)//2
        if t>n:
            print("No")
            exit()
        if t==n:
            print("Yes")
            break
        a+=1
    print(a)
    s=set(range(1,1+n))
    l=[0]*(n+1)
    ans=[set()]

    for i in range(a):
        ll=set()
        for j in ans[:i+1]:
            for p in s&j:
                if p not in ll:
                    ll.add(p)
                    if l[p]==1:
                        s.remove(p)
                    else:
                        l[p]+=1
                    break

        for p in s:
            if len(ll)>=n*2//a:
                break
            else:
                if l[p]==0:
                    ll.add(p)
                    l[p]+=1

        ans.append(ll)
        print(n*2//a,*ll)


if __name__ == '__main__':
    main()








### FIXED CODE ###

def main():
    n=int(input())
    m=int((2*n)**0.5)
    if m*(m+1)==n*2:
        print("Yes")
        m+=1
        print(m)
    else:
        print("No")
        exit()
    
    ans=[[m-1] for i in range(m)]
    c=1
    for i in range(m):
        for j in range(i+1,m):
            ans[i].append(c)
            ans[j].append(c)
            c+=1
    for i in ans:
        print(*i)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

n,x=map(int,input().split())
*a,=map(int,input().split())

v=[i if i<x else x for i in a]
b=[v[i]+v[i+1]<=x for i in range(n-1)]     

while not all(b):
    for i in range(n-2):
        if not b[i] and not b[i+1]:
            v[i+1]-=1
            break
        if not b[i]:
            v[i]-=1
            break
    b=[v[i]+v[i+1]<=x for i in range(n-1)]     
    
print(sum(a)-sum(v))

### FIXED CODE ###

n,x=map(int,input().split())
*a,=map(int,input().split())

v=[i if i<x else x for i in a]

for i in range(n-1):
    if v[i]+v[i+1]>x:
        v[i+1]=x-v[i]

print(sum(a)-sum(v))
### BUGGY CODE ###

s = input()
l = len(s)
r = 0
b = [0]*2019
m = b[:]
for i in range(3,l):
    m2 = b[:]
    for j in range(1,2019):
        j2 = (j*10+int(s[i])) % 2019
        m2[j2] += m[j]
    m2[int(s[i-3:i+1]) % 2019] += 1
    r += m2[0]
    m = m2
print(r)

### FIXED CODE ###

s = input()
s_r = s[::-1]
lmod = [0]
cmod = 0
for n,i in enumerate(s_r):
    cmod += int(i)*pow(10,n,2019) % 2019
    cmod = cmod % 2019
    lmod.append(cmod)

from collections import Counter
r = 0
for _,i in Counter(lmod).items():
    r += i*(i-1)/2

print(int(r))
### BUGGY CODE ###

n, k = list(map(int, input().split()))
mod = 1000000007
nums = [i for i in range(n + 1)]
ans = 0

for i in range(k, n + 2):
	ans += (sum(nums[-1 * i:]) - sum(nums[:i]) + 1) % mod
	ans %= mod
print(ans)


### FIXED CODE ###

n, k = list(map(int, input().split()))
mod = 1000000007
nums = [i for i in range(n + 1)]
ans = 0

for i in range(k, n + 2):
	mx = n * (n + 1) // 2 - (n - i) * (n - i + 1) // 2
	mn = i * (i - 1) // 2
	ans += (mx - mn + 1) % mod
	ans %= mod
print(ans)
### BUGGY CODE ###

N=int(input())
lineup=sorted([int(x) for x in input().split()])
duplicate={}
for i in lineup:
	if i in duplicate:
		duplicate[i]+=1
	else:
		duplicate[i]=1
sieve=[1]*(max(lineup)+2)
counter=0
for i in range(N):
	for j in range(lineup[i]*2,max(lineup)+1,lineup[i]):
		sieve[j]=0

	if duplicate[lineup[i]]==1 and sieve[lineup[i]]==1:
		counter+=1
print(counter)

### FIXED CODE ###

N=int(input())
lineup=sorted([int(x) for x in input().split()])
duplicate={}
for i in lineup:
	if i in duplicate:
		duplicate[i]+=1
	else:
		duplicate[i]=1
b=max(lineup)+1
sieve=[1]*(b)
counter=0
for i in range(N):
	for j in range(lineup[i]*2,b,lineup[i]):
		sieve[j]=0
	if duplicate[lineup[i]]==1 and sieve[lineup[i]]==1:
		counter+=1
print(counter)
### BUGGY CODE ###

import copy

N=int(input())

A=list(map(int,input().split()))

#print(A)

mama=dict()

for i in range(N):

    if(A[i] in mama):
        print(mama[A[i]])
        continue
    
    AA=copy.deepcopy(A)
    ai=A[i]
    del AA[i]
    #print(AA)
    Aset=set(AA)
    count=0
    for i in Aset:
        aa=AA.count(i)
        #print(i,aa)
        count+=int((aa*(aa-1))/2)
    print(count)
    mama[ai]=count


### FIXED CODE ###

from collections import Counter
N=int(input())
A=list(map(int,input().split()))

parent=dict()
An=set(A)
parecou=0
aaa=Counter(A)
for i in aaa.values():
    parecou+=int((i*(i-1)/2))
"""
for i in An:
    f=A.count(i)
    parent[i]=f
    parecou+=int((f*(f-1)/2))
"""


#print(parecou)
for i in range(N):
    anko=aaa[A[i]]
    print(parecou-int((anko*(anko-1)/2))+int(((anko-2)*(anko-1)/2)))
    #print(parecou-anko+1)
### BUGGY CODE ###

import sys
s = str(input())
Q = int(input())
q = sys.stdin.readlines()
for i in q:
  i = i.strip()
  if i[0] == '1':
    s = s[::-1]
  elif i[2] == '1':
    s = i[4] + s
  else:
    s += i[4]
print(s)

### FIXED CODE ###

from collections import deque
import sys
s = deque(list(input()))
Q = int(input())
cnt = 0

for i in range(Q):
  q = list(input().split())
  if q[0] == '1':
    cnt = (cnt+1) % 2
  elif q[1] == '1':
    if cnt == 0:
      s.appendleft(q[2])
    else:
      s.append(q[2])
  else:
    if cnt == 0:
      s.append(q[2])
    else:
      s.appendleft(q[2])

if cnt == 1:
  s.reverse()
print("".join(s))
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
cnt = n

for i in range(n):
    for j in range(i+1):
        if p[i] > p[j]:
            cnt -= 1
            break
print(cnt)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
cnt = 0
minx = max(p)
for i in range(n):
    minx = min(p[i],minx)
    if minx >= p[i]:
        cnt += 1
print(cnt)
### BUGGY CODE ###

h, w, d = map(int, input().split())
X = [None for k in range(h*w)]
for i in range(h):
    *A, = map(int, input().split())
    for j in range(w):
        X[A[j]-1] = (i, j)
D = []
for k in range(h*w):
    if k+d < h*w:
        x0, y0 = X[k]
        x1, y1 = X[k+d]
        D.append(abs(x0-x1)+abs(y0-y1))
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    ans = 0
    for k in range(l-1, r-1, d):
        ans += D[k]
    print(ans)


### FIXED CODE ###

h, w, d = map(int, input().split())
X = [None for k in range(h*w)]
for i in range(h):
    *A, = map(int, input().split())
    for j in range(w):
        X[A[j]-1] = (i, j)
D = []
for k in range(h*w):
    if k < d:
        D.append(0)
    else:
        x0, y0 = X[k]
        x1, y1 = X[k-d]
        D.append(D[k-d]+abs(x0-x1)+abs(y0-y1))
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(D[r-1]-D[l-1])
### BUGGY CODE ###

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
i = 0
if N == 1:
    print(A[0]//(2**M))
else:
    while i < M:
        if A[-2] != 0:
            j = A[-1]//A[-2]
        else:
            j = A[-1]
        if i + j <= M:
            A[-1] //= 2**j
            i += j
        else:
            A[-1] //= 2**(M-i)
            i = M
        A.sort()
    print(sum(A))

### FIXED CODE ###

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse = True)
while M > 0:
    A[0] //= 2
    for i in range(1,M):
        if i < N and A[i] >= A[0]:
            A[i] //= 2
        else:
            M -= i
            A.sort(reverse = True)
            break
    else:
        break
print(sum(A))
### BUGGY CODE ###

Ns,Ms=input().split()
N=int(Ns)
M=int(Ms)
LR=input().split()
ans=set(range(int(LR[0]),int(LR[1])+1))
for i in range(M-1):
	LR=[]
	LR=input().split()
#	print("ssssssssss")
#	print(ans)
	ansy=set(range(int(LR[0]),(int(LR[1])+1)))
	ans=ans&ansy
print(len(ans))


### FIXED CODE ###

Ns,Ms=input().split()
N=int(Ns)
M=int(Ms)
lists=[]
ansmins,ansmaxs=input().split()
ansmin=int(ansmins)
ansmax=int(ansmaxs)
for i in range(M-1):
	tmpmin,tmpmax=input().split()
	if int(tmpmin)>ansmin:
		ansmin=int(tmpmin)
	if int(tmpmax)<ansmax:
		ansmax=int(tmpmax)

if (ansmax-ansmin+1)<0:
	ans=0
else:
	ans=ansmax-ansmin+1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list([int(input()) for i in range(M)])

current_step, prev_step, two_prev_step = 0, 1, 0
for i in sorted(range(N), reverse=True):
    if i in A:
        prev_step, two_prev_step = 0, prev_step
        continue

    current_step = prev_step + two_prev_step
    prev_step, two_prev_step = current_step, prev_step

print(current_step % 1000000007)

### FIXED CODE ###

import sys
max_num = 1000000007
input = sys.stdin.readline
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]

stairs = [1] * (N+1)
for i in A:
    stairs[i] = 0

for i in range(1, N):
    if stairs[i+1] != 0:
        stairs[i+1] = stairs[i] + stairs[i-1]
print(stairs[N] % max_num)
### BUGGY CODE ###

N = int(input())
S = input()

c = 0
for i in range(1000):
    num_str = "{0:0>3}".format(i)
    j = 0
    for s in S:
        if num_str[j] == s:
            j += 1
        if j == 3:
            c += 1
            break

print(c)

### FIXED CODE ###

N = int(input())
S = input()
 
c = 0
for i in range(1000):
    num_str = "{0:0>3}".format(i)
    j = 0
    for s in S:
        if num_str[j] == s:
            j += 1
        if j == 3:
            c += 1
            break
 
print(c)
### BUGGY CODE ###

h, w = [int(i) for i in input().split()]
a = []
b = []
for i in range(h):
    a.append(list(input()))
    for j in range(w):
        if a[i][j] == "#":
            b.append([i, j])

cnt = 0
while True:
    c = []
    for i in range(len(b)):
        y = b[i][0]
        x = b[i][1]
        if y > 0:
            if a[y-1][x] != "#":
                a[y-1][x] = "#"
                c.append([y-1, x])
        if y < h-1:
            if a[y+1][x] != "#":
                a[y+1][x] = "#"
                c.append([y+1, x])
        if x > 0:
            if a[y][x-1] != "#":
                a[y][x-1] = "#"
                c.append([y, x-1])
        if x < w-1:
            if a[y][x+1] != "#":
                a[y][x+1] = "#"
                c.append([y, x+1])
    if len(c) == 0:
        break
    cnt += 1
    b = c
print(cnt)

### FIXED CODE ###

from collections import deque
import sys


H, W = [int(_) for _ in input().split()]

M = []
q = deque([])
for i in range(H):
    A = input()
    M.append(list(A))
    for j in range(W):
        if A[j] == '#':
            q.append([j, i, 0])

depth_now = 0
depth = 0
count = 0
while len(q) > 0:
    p = q.popleft()
    x = p[0]
    y = p[1]
    depth = p[2]
    if x - 1 >= 0 and M[y][x-1] == '.':
        q.append([x-1, y, depth+1])
        M[y][x-1] = '#'
    if x + 1 < W and M[y][x+1] == '.':
        q.append([x+1, y, depth+1])
        M[y][x+1] = '#'
    if y - 1 >= 0 and M[y-1][x] == '.':
        q.append([x, y-1, depth+1])
        M[y-1][x] = '#'
    if y + 1 < H and M[y+1][x] == '.':
        q.append([x, y+1, depth+1])
        M[y+1][x] = '#'
print(depth)
### BUGGY CODE ###

n = int(input())
s = list(input())
r = s.count("R")
g = s.count("G")
b = s.count("B")
ans = r*g*b

for i in range(n):
    for j in range(i+1,n):
        k = 2*j - i
        if k > n-1:
            continue
        x = s[i]
        y = s[j]
        z = s[k]

        if x!= y and y != z and z != x:
            ans -= 1

print(ans)

### FIXED CODE ###

n = int(input())
s = list(input())
r = 0
g = 0
b = 0

for c in s:
    if c == "R":
        r += 1
    if c == "G":
        g += 1
    if c == "B":
        b += 1
ans = r*g*b

for i in range(n):
    for j in range(i+1,n):
        k = 2*j - i
        if k > n-1:
            continue
        x = s[i]
        y = s[j]
        z = s[k]
        if x!= y and y != z and z != x:
            ans -= 1

print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
a = [0] + list(map(int, input().split()))  # 1-indexed


journey = [1]  # 道順

for i in range(2**n):
    nxt = a[journey[-1]]
    journey.append(nxt)

if k <= n:
    print(journey[k])
    exit()

# k > n
loop_end = journey[n]

loop_start = n - 1  # ループの始まりのindex

while(journey[loop_start] != loop_end):
    loop_start -= 1

period = loop_end - loop_start

k %= period

while k < n:
    k += period
    
print(journey[period])
    

### FIXED CODE ###

from collections import defaultdict

n, k = map(int, input().split())
*a, = map(int, input().split())
a = [a[i] - 1 for i in range(n)]
ans = 0

if k <= n:
    i = 0
    while(k > 0):
        ans = a[i]
        i = a[i]
        k -= 1
        # print(ans + 1)
    ans += 1

else:
    # 周期の場所をチェック
    start_period = 1
    period_i = -1
    d = defaultdict(int)
    d[0] = 1
    i = 0
    count = 1
    while(1):
        # print(f'i = {i}, count = {count}')
        if a[i] in d.keys():
            period_i = count
            start_period = d[a[i]]
            break

        d[a[i]] = count + 1
        i = a[i]
        count += 1
        
    # 逆引き
    d_r = {i:k for k, i in d.items()}
    # print('d: ', d)
    # print('d_r: ', d_r)
    # print('period_i:', period_i)
    # print('start_period:', start_period)
    # print(f'{k - (start_period - 1)}')
    # print(f'{(k - (start_period - 1)) % (period_i - start_period + 1)}')
    # print('d_r[start_period]: ', d_r[start_period])
    # print(d_r[start_period + ((k - (start_period - 1)) % (period_i - start_period + 1))])
    ans = d_r[start_period + ((k - (start_period - 1)) % (period_i - start_period + 1))] + 1
    
    
print(ans)
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(n):
    for j in range(i,n):
        if sum(A[i:j+1]) == 0:
            ans += 1
print(ans)

### FIXED CODE ###

from itertools import accumulate
from collections import Counter
n = int(input())
nums = list(map(int,input().split()))
s = [0]+list(accumulate(nums))
ans = 0
for i in Counter(s).values():
    if i > 1:
        ans += i * (i - 1) // 2
print(ans)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
 
a_ = list(set(a))

temp = {}
for i in a_:
    temp[i] = a.count(i)

temp3 = []
for i in a_:
    if i in temp:
        a1 = temp[i]
    else :
        a1 = 0

    if i+1 in temp:
        a2 = temp[i+1]
    else :
        a2 = 0

    if i-1 in temp:
        a3 = temp[i-1]
    else :
        a3 = 0
        
    temp3.append(a1+a2+a3)
 
print(max(temp3))

### FIXED CODE ###


import sys  
import numpy as np
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
k = [0] * max(3,(max(a)+1))

for p in a:
    k[p] += 1
ans = 0
for q,r,s in zip(k, k[1:] , k[2:]):
    ans = max(ans, q+r+s)

print(ans)
### BUGGY CODE ###

N = int(input())
A = sorted([int(i) for i in input().split()])

ans = 0
while len(A) > 0:
    if len(A) == 1:
        ans += 1
    elif A[0] != A[1]:
        ans += 1
    A = [i for i in A if i % A[0] != 0]
    
print(ans)

### FIXED CODE ###

from collections import Counter

N = int(input())
A = [int(i) for i in input().split()]
num = set(A)
count = Counter(A)
dp = [True] * (10**6 + 1)

for a in num:
    for n in range(a+a, 10**6+1, a):
        dp[n] = False

ans = 0
for a in num:
    if count[a] == 1 and dp[a] == True:
        ans += 1

print(ans)
### BUGGY CODE ###

r,g,b,n = map(int,input().split())

cnt = 0
for i in range(n//r+1):
  for j in range(n//g+1):
    k = (n - i*r - j*g)/b
    if k>=0 and k.is_integer():
      cnt+=1
print(cnt)


### FIXED CODE ###

r,g,b,n = map(int,input().split())

cnt = 0
for i in range(n//r+1):
  for j in range(n//g+1):
    k = (n - i*r - j*g)/b
    if k>=0 and k.is_integer():
      cnt+=1
print(cnt)
### BUGGY CODE ###

#
X, Y = list(map(int, input().split()))

#
if X==Y or Y==1:
    print(-1)
    exit()

#
N = X*2
while N<=10**18:
    if N%Y!=0:
        print(N)
        exit()
    N += X

#
print(-1)


### FIXED CODE ###

#
X, Y = list(map(int, input().split()))

#
if X==Y or Y==1 or X%Y==0:
    print(-1)
    exit()

#
N = X*2
while N<=10**18:
    if N%Y!=0:
        print(N)
        exit()
    N += X

#
print(-1)
### BUGGY CODE ###

#一個だけRE、わからねえ
#解答見る
import sys
sys.setrecursionlimit(10000)
h,w=map(int,input().split())

def go_next(I,J):
    global dp,w,h
    if 0<=I<h-1:
        if x[I+1][J]=="." and dp[I+1][J]>dp[I][J]+1:
            dp[I+1][J]=dp[I][J]+1
            go_next(I+1,J)
    if 0<I<=h-1:
        if x[I-1][J]=="." and dp[I-1][J]>dp[I][J]+1:
            dp[I-1][J]=dp[I][J]+1
            go_next(I-1,J)
    if 0<=J<w-1:
        if x[I][J+1]=="." and dp[I][J+1]>dp[I][J]+1:
            dp[I][J+1]=dp[I][J]+1
            go_next(I,J+1)
    if 0<J<=w-1:
        if x[I][J-1]=="." and dp[I][J-1]>dp[I][J]+1:
            dp[I][J-1]=dp[I][J]+1
            go_next(I,J-1)

x=[]
for i in range(h):
    x.append(list(input()))
#print(x)
c=0
for i in range(h):
    for j in range(w):
        if x[i][j]==".":
            c+=1
dp=[[10000000000 for i in range(w)]for j in range(h)]
dp[0][0]=1
go_next(0,0)
if dp[h-1][w-1]==10000000000:
    print(-1)
else:
    print(c-dp[h-1][w-1])


### FIXED CODE ###

#一個だけRE、わからねえ
#解答見る
import sys
sys.setrecursionlimit(1005)
h,w=map(int,input().split())

def go_next(I,J,n):
    n+=1
    global dp,w,h
    if n>1000:
        return
    if 0<=I<h-1:
        if x[I+1][J]=="." and dp[I+1][J]>dp[I][J]+1:
            dp[I+1][J]=dp[I][J]+1
            go_next(I+1,J,n)
    if 0<I<=h-1:
        if x[I-1][J]=="." and dp[I-1][J]>dp[I][J]+1:
            dp[I-1][J]=dp[I][J]+1
            go_next(I-1,J,n)
    if 0<=J<w-1:
        if x[I][J+1]=="." and dp[I][J+1]>dp[I][J]+1:
            dp[I][J+1]=dp[I][J]+1
            go_next(I,J+1,n)
    if 0<J<=w-1:
        if x[I][J-1]=="." and dp[I][J-1]>dp[I][J]+1:
            dp[I][J-1]=dp[I][J]+1
            go_next(I,J-1,n)

x=[]
for i in range(h):
    x.append(list(input()))
#print(x)
c=0
for i in range(h):
    for j in range(w):
        if x[i][j]==".":
            c+=1
dp=[[10000000000 for i in range(w)]for j in range(h)]
dp[0][0]=1
go_next(0,0,0)
if dp[h-1][w-1]==10000000000:
    print(-1)
else:
    print(c-dp[h-1][w-1])
### BUGGY CODE ###

N,M,Q = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(Q)]
L.sort(key=lambda x: x[0])
ans = 0
for bit in range(1 << Q):
    sumnum = 0
    flag = True
    A = [0]*(N+1)
    s = set()
    for i in range(Q):
        if bit & (1 << i):
            if not L[i][0]-1 in s:
                s.add(L[i][0]-1)
            if not L[i][1]-1 in s:
                s.add(L[i][1]-1)
                A[L[i][1]-1] = A[L[i][0]-1]+L[i][2]
            if L[i][1]-1 in s:
                if A[L[i][1]-1] - A[L[i][0]-1] != L[i][2]:
                    flag = False
                    break
                else:
                    sumnum += L[i][3]
    
    if flag:
        ans = max(ans, sumnum)

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7) 
N,M,Q = map(int, input().split())
a = [0]*Q
b = [0]*Q
c = [0]*Q
d = [0]*Q
for i in range(Q):
    a[i],b[i],c[i],d[i] = map(int, input().split())

ans = 0
def dfs(L):
    global ans
    if len(L) == N+1:
        sumnum = 0
        for i in range(Q):
            if L[b[i]] - L[a[i]]==c[i]:
                sumnum += d[i]
        ans = max(ans, sumnum)
        return 0
    A = L.copy()
    A.append(A[-1])
    while A[-1] <= M:
        dfs(A)
        A[-1]+=1

dfs([1])
print(ans)