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

import sys
h,w,m = map(int,input().split())
h_lst = [0]*h
w_lst = [0]*w
memo = []

for i in range(m):
  x,y = map(int,input().split())
  h_lst[x-1] += 1
  w_lst[y-1] += 1
  memo.append((x-1,y-1))

sh = 0
for i in range(h):
  if h_lst[i] > sh:
    sh = h_lst[i]
sw = 0
for i in range(w):
  if w_lst[i] > sw:
    sw = w_lst[i]



memo = set(memo)
              

for i in range(h):
  if h_lst[i] == sh:
    for j in range(w):
      if (i,j) not in memo and w_lst[j] == sw:
        print(sh+sw)
        sys.exit()
print((sh+sw)-1)        
  

### FIXED CODE ###

import sys
h,w,m = map(int,input().split())
h_lst = [[0,i] for i in range(h)]
w_lst = [[0,i] for i in range(w)]
memo = []

for i in range(m):
  x,y = map(int,input().split())
  h_lst[x-1][0] += 1
  w_lst[y-1][0] += 1
  memo.append((x-1,y-1))

h_lst.sort(reverse = True)
w_lst.sort(reverse = True)
Max_h = h_lst[0][0]
Max_w = w_lst[0][0]
h_ans = [h_lst[0][1]]
w_ans = [w_lst[0][1]]
if h != 1:
  s = 1
  while s < h and h_lst[s][0] == Max_h:
    h_ans.append(h_lst[s][1])
    s+= 1  
if w!= 1:  
  t=1  
  while t < w and w_lst[t][0] == Max_w:
    w_ans.append(w_lst[t][1])
    t += 1
  

memo = set(memo)

#探索するリストは、最大を取るものの集合でなければ計算量はO(m)にはならない！             
for j in h_ans:
  for k in w_ans:
    if (j,k) not in memo:
      print(Max_h+Max_w)
      sys.exit()
print((Max_h+Max_w)-1)
### BUGGY CODE ###

n = int(input())
m = list(map(int,input().split()))
m.sort()

ans = 0
for i in range(n):
    for j in range(i+1,n):
        l = j
        r = n
        while r-l>1:
            mid = (r+l)//2
            if m[mid] < m[i]+m[j] and m[i] < m[mid]+m[j] and m[j] < m[mid]+m[i]:
                l = mid
            else:
                r = mid
        ans += l-j

print(ans)

### FIXED CODE ###

n = int(input())
m = list(map(int,input().split()))
m.sort()

ans = 0
for i in range(n):
    for j in range(i+1,n):
        l = j
        r = n
        while r-l>1:
            mid = (r+l)//2
            if m[mid] < m[i]+m[j] and m[i] < m[mid]+m[j] and m[j] < m[mid]+m[i]:
                l = mid
            else:
                r = mid
        ans += l-j

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

def main():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]

    que = []
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                que.append((h, w))

    ans = 0
    while que:
        # print(A)
        # print(len(que))
        q = []
        for h, w in que:
            dx4 = [0, 0, 1, -1]
            dy4 = [1, -1, 0, 0]
            for dx, dy in zip(dx4, dy4):
                nh = min(max(0, h + dy), H - 1)
                nw = min(max(0, w + dx), W - 1)

                if A[nh][nw] == '.':
                    q.append((nh, nw))
                    A[nh][nw] = '#'

        que = q

        if que:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect


def main():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]

    checked = [[False] * W for _ in range(H)]
    ans = 0

    que = []
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' and not checked[h][w]:
                que.append((h, w))
                checked[h][w] = True
    while que:
        next_que = []
        while que:
            h, w = que.pop()
            dx4 = [0, 0, 1, -1]
            dy4 = [1, -1, 0, 0]

            for dx, dy in zip(dx4, dy4):
                next_h = h + dy
                next_w = w + dx
                if 0 <= next_h < H and 0 <= next_w < W and A[next_h][next_w] == '.' and not checked[next_h][next_w]:
                    A[next_h][next_w] = '#'
                    checked[h][w] = True
                    next_que.append((next_h, next_w))
        que = next_que
        if que:
            ans += 1

    print(ans)


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

N,K = map(int, input().split())
H = map(int, input().split())
T = list(H)
if K>=N:
    print("0")
else:
    T.sort(reverse = True)
    for i in range(K):
        del T[0]
    
    print(sum(T))

### FIXED CODE ###

N,K = map(int, input().split())
T = list(map(int, input().split()))
T.sort()
if K>=N:
    print(0)
else:
    for i in range(K):
        T.pop()
    
    print(sum(T))
### BUGGY CODE ###

N,M,K = list(map(int,input().split(' ')))

friend_list = [0]*(N+1)
bad_list = [0]*(N+1)
group = {}

parent = [i for i in range(N+1)]

def find(i):
    while parent[i] != i:
        i = parent[i]
    return i

def union(i, j):
    i = find(i)
    j = find(j)
    parent[j] = i



for i in range(M):
    A,B = list(map(int,input().split(' ')))
    friend_list[A]+=1
    friend_list[B]+=1
    
    union(A,B)

for i in range(K):
    A,B = list(map(int,input().split(' ')))
    if find(A)==find(B):
        bad_list[A]+=1
        bad_list[B]+=1
    
    #union(A,B)



#print(parent)
#print('parent')
for i in range(1,N+1):
    oya = find(i)
    parent[i] = oya
    #print(oya)
    if oya in group:
        group[oya] = group[oya]+1
    else:
        group[oya]=1
#print('friend')
#print(friend_list)
#print('bad')
#print(bad_list) 
#print(group)

kouho = [0]*N

for i in range(1,N+1):
    oya = find(i)
    abc = group[oya]-friend_list[i]-bad_list[i]-1
    kouho[i-1] = abc

for k in kouho:
    print(k,end=" ")
print()

### FIXED CODE ###

N,M,K = list(map(int,input().split(' ')))

friend_list = [0]*(N+1)
bad_list = [0]*(N+1)
group = {}

parent = [i for i in range(N+1)]

def find(i):
    rireki = []
    while parent[i] != i:
        rireki.append(i)
        i = parent[i]
    for r in rireki:
        parent[r]=i
    return i

def union(i, j):
    i = find(i)
    j = find(j)
    parent[j] = i



for i in range(M):
    A,B = list(map(int,input().split(' ')))
    friend_list[A]+=1
    friend_list[B]+=1
    
    union(A,B)

for i in range(1,N+1):
    oya = find(i)
    parent[i] = oya
    #print(oya)
    if oya in group:
        group[oya] = group[oya]+1
    else:
        group[oya]=1

for i in range(K):
    A,B = list(map(int,input().split(' ')))
    if find(A)==find(B):
        bad_list[A]+=1
        bad_list[B]+=1
    
    #union(A,B)



#print(parent)
#print('parent')

#print('friend')
#print(friend_list)
#print('bad')
#print(bad_list) 
#print(group)

kouho = [0]*N

for i in range(1,N+1):
    oya = find(i)
    abc = group[oya]-friend_list[i]-bad_list[i]-1
    kouho[i-1] = abc

for k in kouho:
    print(k,end=" ")
print()

#print(parent)
### BUGGY CODE ###

a,b,n=map(int,input().split())
import math
x=b-1
if n<b-1:
    m=[math.floor(a*n/b)]
else: m=[0]
while x<=n:
    f=math.floor(a*x/b)-a*(math.floor(x/b))
    m.append(f)
    x+=b
print(max(m))

### FIXED CODE ###

a,b,n=map(int,input().split())
import math
if n<b:
    m=math.floor(a*n/b)
else:
    e=b-1
    m=math.floor(a*e/b)
print(m)
### BUGGY CODE ###

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]

dp = [[0 for i in range(W+1)] for i in range(N+1)]

for i in range(N):
    w, v = wv[i]
    for sum_weight in range(W+1):
        if sum_weight - w >= 0:
            dp[i+1][sum_weight] = max(dp[i+1][sum_weight], dp[i][sum_weight-w] + v)
        dp[i+1][sum_weight] = max(dp[i+1][sum_weight], dp[i][sum_weight])

print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())

weight = [0] * N
value = [0] * N
for i in range(N):
    w, v = map(int, input().split())
    weight[i], value[i] = w, v

dp = [[0]*(W+1) for _ in range(N)]
for i in range(weight[0], W+1):
    dp[0][i] = value[0]

for i in range(1, N):
    for ws in range(W+1):
        if ws - weight[i] >= 0:
            dp[i][ws] = dp[i-1][ws - weight[i]] + value[i]
        dp[i][ws] = max(dp[i][ws], dp[i-1][ws])

print(dp[N-1][W])
### BUGGY CODE ###

f=lambda:map(int,input().split())
R,C,K=f()
g=[[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
  r,c,v=f()
  g[r][c]=v
dp=[[[0]*4 for _ in range(C+2)] for _ in range(R+2)]
for i in range(1,R+1):
  for j in range(1,C+1):
    for k in range(3,-1,-1):
      if k: dp[i][j][k]=max(dp[i][j][k],dp[i][j][k-1]+g[i][j])
      dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][k])
      dp[i][j+1][k]=max(dp[i][j+1][k],dp[i][j][k])
print(max(dp[R][C][k] for k in range(4)))

### FIXED CODE ###

f=lambda:map(int,input().split())
R,C,K=f()
g=[[0]*(R+1) for _ in range(C+1)]
for _ in range(K):
  r,c,v=f()
  g[c][r]=v
dp=[[0]*4 for _ in range(R+1)]
for i in range(1,C+1):
  for j in range(1,R+1):
    t=g[i][j]
    if t:
      for k in range(3,0,-1):
        dp[j][k]=max(dp[j][k],dp[j][k-1]+t)
      dp[j][1]=max(dp[j][k],max(dp[j-1])+t)
    dp[j][0]=max(dp[j][0],max(dp[j-1]))
print(max(dp[R]))
### BUGGY CODE ###

def inputs(): return (int(x) for x in input().split())
N,M,K = inputs()
f = {i:[] for i in range(N)}
b = {i:[] for i in range(N)}
ans = [0]*(N)
for _ in range(M):
    x,y = [int(x) for x in input().split()]
    f[x-1].append(y-1)
    f[y-1].append(x-1)
for _ in range(K):
    x,y = inputs()
    b[x-1].append(y-1)
    b[y-1].append(x-1)
for i in range(N):
    visited =visited = {i: False for i in range(N)}
    stk = [(i,-1,0)]
    while stk:
        v,p,l = stk.pop()
        if visited[v]:
            continue
        visited[v] = True
        if 1<l and not v in b[i] and not v in f[i]:
            ans[i]+=1
        for u in f[v]:
            if u !=p:
                stk.append((u,v,l+1))
print(*ans)

### FIXED CODE ###

def inputs(): return (int(x) for x in input().split())
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
N,M,K = inputs()
uf = UnionFind(N+1)
f = {i:[] for i in range(N)}
b = {i:[] for i in range(N)}
ans = [0]*(N)
for _ in range(M):
    x,y = [int(x) for x in input().split()]
    f[x-1].append(y-1)
    f[y-1].append(x-1)
    uf.union(x-1,y-1)
for _ in range(K):
    x,y = inputs()
    if uf.same(x-1,y-1):
        b[x-1].append(y-1)
        b[y-1].append(x-1)
for i in range(N):
    ans[i]+=uf.size(i)-len(f[i])-len(b[i])-1
print(*ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
import heapq
n,x,y = map(int,input().split())
G = [[]*n for i in range(n)]
for i in range(n-1):
  G[i].append((i+1))
  G[i+1].append(i)
x-=1;y-=1
G[x].append((y))
G[y].append((x))
# print(G)
def bfs(g,s):
    n=len(g)
    dist = [inf]*n
    dist[s] = 0
    q = collections.deque()
    q.append(s)
    while q:
        u = q.popleft()
        for v in g[u]:
            if dist[v] != inf:continue
            dist[v] = dist[u] + 1
            q.append(v)
    return dist
sets = [set() for i in range(n)]
for i in range(n-1):
  dist = bfs(G,i)
  for j in range(n):
    sets[dist[j]].add((min(i,j),max(i,j)))
for i in range(1,n):
  print(len(sets[i]))
    


### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
import heapq
n,x,y = map(int,input().split())
G = [[]*n for i in range(n)]
for i in range(n-1):
  G[i].append((i+1))
  G[i+1].append(i)
x-=1;y-=1
G[x].append((y))
G[y].append((x))
# print(G)
def bfs(g,s):
    n=len(g)
    dist = [inf]*n
    dist[s] = 0
    q = collections.deque()
    q.append(s)
    while q:
        u = q.popleft()
        for v in g[u]:
            if dist[v] != inf:continue
            dist[v] = dist[u] + 1
            q.append(v)
    return dist
D = [0]*n
for i in range(n-1):
  dist = bfs(G,i)
  for j in range(i+1,n):
    D[dist[j]] += 1
for i in range(1,n):
  print(D[i])
### BUGGY CODE ###

n = int(input())

pw = 1
num = 1
for i in range(n):
  pw = pw  * num
  num += 1
  
print(pw % (10**9+7))

### FIXED CODE ###

n = int(input())

pw = 1
num = 1
for i in range(n):
  pw = pw*num % (10**9+7)
  num += 1
  
print(pw)
### BUGGY CODE ###

n = int(input())

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

l = [0] * (3*n)

first = a[0:n]
second = a[2*n:3*n]

x = [0] * (3*n)
y = [0] * (3*n)

x[n-1] = sum(first)
y[2*n-1] = sum(second)

for i in range(n,2*n):
    first.append(a[i])
    first.remove(min(first))
    x[i] = sum(first)

for i in range(n,2*n):
    second.append(a[-i-1])
    second.remove(max(second))
    y[-i-2] = sum(second)
    
for i in range(n-1,2*n):
    l[i] = x[i] - y[i]
    
#print(x)
#print(y)
#print(l)

print(max(l[n-1:2*n]))

### FIXED CODE ###

import heapq

n = int(input())

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

func = lambda p: p * (-1)

b = list(map(func,a[:]))

#print(a)
#print(b)

l = [0] * (3*n)

first = a[0:n]
second = b[2*n:3*n]

x = [0] * (3*n)
y = [0] * (3*n)

x[n-1] = sum(first)
y[2*n-1] = sum(second)

heapq.heapify(first)
heapq.heapify(second)

for i in range(n,2*n):
    heapq.heappush(first, a[i])
    s = first[0]
    heapq.heappop(first)
    x[i] = x[i-1] + a[i] - s

for i in range(n,2*n):
    heapq.heappush(second, b[-i-1])
    t = second[0]
    heapq.heappop(second)
    y[-i-2] = y[-i-1] + b[-i-1] - t
    
for i in range(n-1,2*n):
    l[i] = x[i] + y[i]
    
#print(x)
#print(y)
#print(l)

print(max(l[n-1:2*n]))
### BUGGY CODE ###

a,b,k = [int(i) for i in input().split()]
A = [i for i in range(a,b+1)]
n = len(A)
ans = []
if n <= 2*k:
    for a in A:
        print(a)

else:
    A = A[:k]+A[-k:]
    for a in A:
        print(a)

### FIXED CODE ###

a,b,k = [int(i) for i in input().split()]
n = b-a+1

if n <= 2*k:
    for i in range(a,b+1):
        print(i)

else:
    for i in range(k):
        print(a+i)
    for i in range(b-k+1,b+1):
        print(i)
### BUGGY CODE ###

MOD = 10 ** 9 + 7
S = input()

dp = [0] * 13
dp[0] = 1

for s in S:
  prev = dp.copy()
  dp = [0] * 13
  if s == '?':
    add = range(10)
  else:
    add = [int(s)]
  for i in range(13):
    for x in add:
      dp[(10*i+x)%13] += prev[i]
  dp = [x % MOD for x in dp]
  
print(dp[5])


### FIXED CODE ###

MOD = 10 ** 9 + 7
S = input()

dp = [0] * 13
dp[0] = 1

for s in S:
  prev = [x for x in dp]
  dp = [0] * 13
  if s == '?':
    add = range(10)
  else:
    add = [int(s)]
  for i in range(13):
    for x in add:
      dp[(10*i+x)%13] += prev[i]
  dp = [x % MOD for x in dp]
  
print(dp[5])
### BUGGY CODE ###

import sys

def input():
    return sys.stdin.readline().strip()

def main():
    K = int(input())
    S = input()

    mod = 10 ** 9 + 7
    n = len(S)
    ans = 0

    fact =[1]*(K+n)
    factinv = [1]*(K+n)
    inv = [0,1]


    for i in range(2,K+n):
        fact[i] = (fact[i-1] * i) % mod
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv[i] = (factinv[i-1] * inv[i]) % mod

    def nCr(n,r):
        r = min(r,n-r)
        return (fact[n] * factinv[r] * factinv[n-r]) % mod

    for i in range(K+1):
        tmp = 25 ** i % mod
        tmp *= nCr(i+n-1,n-1)
        tmp *= 26 ** (K-i) % mod
        ans += tmp
        ans %= mod
        #ans += ((25 ** i * nCr(i+n-1,n-1)) * (26 ** (K - i))) % mod
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def input():
    return sys.stdin.readline().strip()

def main():
    K = int(input())
    S = input()

    mod = 10 ** 9 + 7
    n = len(S)
    ans = 0

    fact =[1]*(K+n)
    factinv = [1]*(K+n)
    inv = [0,1]


    for i in range(2,K+n):
        fact[i] = (fact[i-1] * i) % mod
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv[i] = (factinv[i-1] * inv[i]) % mod

    def nCr(n,r):
        r = min(r,n-r)
        return (fact[n] * factinv[r] * factinv[n-r]) % mod

    for i in range(K+1):
        tmp = pow(25,i,mod)
        tmp *= nCr(i+n-1,n-1)
        tmp *= pow(26,K-i,mod)
        ans += tmp
        ans %= mod
    print(ans)

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

import bisect as bi
import sys
from operator import itemgetter
input = sys.stdin.readline

n,m = map(int,input().split())
a = list(map(int,input().split()))
b = [0] * m
for i in range(m):
    b[i] = list(map(int,input().split()))

ans = 0
b.sort(key=itemgetter(1),reverse=True)
for i in b:
  for j in range(i[0]):
    a.append(i[1])
a.sort(reverse=True)
for i in range(n):
  ans += a[i]
print(ans)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from operator import itemgetter

N,M = map(int,readline().split())
A = list(map(int,readline().split()))
m = map(int,read().split())
BC = list(zip(m,m))

BC.sort(key = itemgetter(1),reverse=True)

BC.append((N,-1))

change = []
for b,c in BC:
    change += [c] * b
    if len(change) > N:
        break

A += change
A.sort()
answer = sum(A[-N:])
print(answer)
### BUGGY CODE ###

X,Y,Z,K = map(int, input().split())
A = [int(i) for i in input().split()] 
B = [int(i) for i in input().split()] 
C = [int(i) for i in input().split()] 

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

def solve(P):
    cnt = 0
    for x in range(X):
        for y in range(Y):
            for z in range(Z):
                if A[x]+B[y]+C[z] >= P:
                    cnt+=1
                if cnt >= K:
                    return False
    return True

t = True
P = A[0]+B[0]+C[0]
while t:
    t = solve(P)
    P -= 1


ans = []
cnt = 0
for x in range(X):
        for y in range(Y):
            for z in range(Z):
                if A[x]+B[y]+C[z] >= P+1:
                    ans.append(A[x]+B[y]+C[z])
                    cnt+=1
                if cnt >= K:
                    ans.sort(reverse=True)
                    for k in range(K):
                        print(ans[k])
                    exit()

### FIXED CODE ###

X,Y,Z,K = map(int, input().split())
A = [int(i) for i in input().split()] 
B = [int(i) for i in input().split()] 
C = [int(i) for i in input().split()] 

ans = []
for x in range(X):
    for y in range(Y):
        ans.append(A[x]+B[y])

ans.sort(reverse=True)
C.sort(reverse=True)
ans2 = []
for k in range(min(K,X*Y)):
    for z in range(min(Z,K)):
        ans2.append(ans[k]+C[z])
ans2.sort(reverse=True)

for k in range(K):
    print(ans2[k])
### BUGGY CODE ###

# D - Multiple of 2019

s = str(input())
ans = 0
 
for i in range(len(s)):
    for j in range(i+4, min(len(s),10000)):
        if int(s[i:j+1])%2019==0:
            ans += 1
 
print(ans)

### FIXED CODE ###

# D - Multiple of 2019

from collections import defaultdict
d = defaultdict(int)

mod = 2019
s = str(input())[::-1]

ssum = 0
d[0] = 1
for i in range(len(s)):
    ssum = (ssum + int(s[i])*pow(10, i, mod))%mod
    d[ssum] += 1

ans = 0
for n in d.values():
    ans += n*(n-1)//2

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

import math

def solve(a,n,k):
  dp = [0]*(n)
  dp[0]=0
  inf = 10**9
  for i in range(1,n):
    dp[i]=inf
    r=max(0,i-k)
    for j in range(r,i):
      dp[i]=min(dp[i],abs(a[i]-a[j])+dp[j])

  #print(dp)
  return dp[n-1]
n,k=map(int,input().split())
a=list(map(int,input().split()))
print(solve(a,n,k))


### FIXED CODE ###

import math
 
def solve(a,n,k):
  dp = [0]*(n)
  dp[0]=0
  inf = 10**9
  for i in range(1,n):
    dp[i]=inf
    r=max(0,i-k)
    dp[i]=min([abs(a[i]-a[j])+dp[j] for j in range(r,i)])
 
  #print(dp)
  return dp[-1]
n,k=map(int,input().split())
a=list(map(int,input().split()))
print(solve(a,n,k))
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())
V = []
for i in range(M):
    a, b = map(int, input().split())
    V.append((a, b))


def bfs(G):
    if len(G[1]) >= 2:
        return 0
    visited = [False]*N
    visited[0] = True
    que = deque([(1, -1)])
    while que:
        ci, p = que.popleft()
        if len(G[ci]) >= 3:
            return 0
        for ni in G[ci]:
            if ni != p:
                if visited[ni-1]:
                    return 0
                visited[ni-1] = True
                que.append((ni, ci))
    if all(visited):
        return 1
    else:
        return 0


ans = 0
for i in range(2 ** M):
    if bin(i).count('1') != N-1:
        continue
    else:
        G = {k: [] for k in range(N+1)}
        for j in range((2**M).bit_length()):  # このループが一番のポイント
            if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
                (a, b) = V[j]
                # 無向グラフ
                G[a].append(b)
                G[b].append(a)
        ans += bfs(G)
print(ans)


### FIXED CODE ###

import itertools

N,M=map(int,input().split())
route=[list(map(int,input().split())) for _ in range(M)]
candidate=list(itertools.permutations(range(1,N+1)))

ans=0
for c in candidate:
  if c[0]==1:
    for i in range(N-1):
      l=sorted([c[i], c[i+1]])
      if l not in route:
         break
    else:
      ans+=1
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
gate = [0] * N
maxL, minR = 0, N
for i in range(M):
    L, R = map(int, input().split())
    maxL = max(maxL, L-1)
    minR = min(minR, R-1)
    for j in range(maxL, minR+1):
        gate[j] += 1

count = 0
for k in gate:
    if k == M:
        count += 1
print(count)


### FIXED CODE ###

N, M = map(int, input().split())
gate = [0] * N
maxL, minR = 0, N
for i in range(M):
    L, R = map(int, input().split())
    maxL = max(maxL, L-1)
    minR = min(minR, R-1)

count = minR - maxL + 1
if count >= 0:
    print(count)
else:
    print(0)
### BUGGY CODE ###

N,K=map(int, input().split()) 
R,S,P=map(int, input().split()) 
T=input()
SC=0

def MaxScore(n,t):
    SC = 0
    Z=[0]*n
    if t[0]=='r':
        Z[0]='p'
        SC+=P
    elif t[0]=='s':
        Z[0]='r'
        SC+=R
    else:
        Z[0]='s'
        SC+=S
    for i in range(1,n):
        if t[i]=='r':
            if Z[i-1]!='p':
                Z[i]='p'
                SC+=P
            elif t[min([i+1,n-1])]=='p':
                Z[i]='r'
            else:
                Z[i]='s'
        elif t[i]=='s':
            if Z[i-1]!='r':
                Z[i]='r'
                SC+=R
            elif t[min([i+1,n-1])]=='r':
                Z[i]='s'
            else:
                Z[i]='p'
        else:
            if Z[i-1]!='s':
                Z[i]='s'
                SC+=S
            elif t[min([i+1,n-1])]=='s':
                Z[i]='p'
            else:
                Z[i]='r'        
    return Z,SC

for i in range(K):
    Ti=[T[j] for j in range(N) if j%K==i ]
    Ti=''.join(Ti)
    if (N-i)%K==0:
        Ni=(N-i)//K
    else:
        Ni=(N-i)//K+1
    Zi,SCi=MaxScore(Ni,Ti)
    SC+=SCi
    
print(SC)

### FIXED CODE ###

N,K=map(int, input().split()) 
R,S,P=map(int, input().split()) 
T=input()
SC=0

def point(w):
    if w=='r':
        return P
    elif w=='s':
        return R
    else:
        return S
    
Flag=[True for i in range(N)]

for i in range(N):
    if Flag[i]:
        SC+=point(T[i])
        if i+K<N and T[i]==T[i+K]:
            Flag[i+K]=False
print(SC)