Harryxun/stf_run huggingface dataset:
h, w = map(int, input().split())
s = [input() for _ in range(h)]

def bfs(x, y):
    q = []
    dp = {}
    def qpush(x, y, t):
        if 0 <= x < w and 0 <= y < h and s[y][x] != '#' and (x, y) not in dp:
            q.append((x, y))
            dp[(x, y)] = t

    qpush(x, y, 0)
    while len(q) > 0:
        (x, y) = q.pop(0)
        qpush(x + 1, y, dp[(x, y)] + 1)
        qpush(x, y - 1, dp[(x, y)] + 1)
        qpush(x - 1, y, dp[(x, y)] + 1)
        qpush(x, y + 1, dp[(x, y)] + 1)
    return (dp[(x, y)], x, y)

(t, x, y) = bfs(0, 0)
(t, x, y) = bfs(x, y)
print(t)


### FIXED CODE ###

h, w = map(int, input().split())
s = [input() for _ in range(h)]

def bfs(x, y):
    q = []
    dp = {}
    def qpush(x, y, t):
        if 0 <= x < w and 0 <= y < h and s[y][x] != '#' and (x, y) not in dp:
            q.append((x, y))
            dp[(x, y)] = t

    qpush(x, y, 0)
    while len(q) > 0:
        (x, y) = q.pop(0)
        qpush(x + 1, y, dp[(x, y)] + 1)
        qpush(x, y - 1, dp[(x, y)] + 1)
        qpush(x - 1, y, dp[(x, y)] + 1)
        qpush(x, y + 1, dp[(x, y)] + 1)
    return dp.get((x, y), 0)

t = 0
for y in range(h):
    for x in range(w):
        t = max(t, bfs(x, y))
print(t)
from numpy import*
n, m = map(int, input().split())
l = []
for i in range(m):
    *a,=map(int,input().split())
    l.append(a[1:])
*p,=map(int,input().split())
ans = 0
for t in range(2**n):
    for s in range(n):
        tmp = array([t >> s & 1])
    for i in l:
        if p == sum(tmp[array(i)-1])%2:
            ans += 1
print(ans)

### FIXED CODE ###

#1107
import math
A, P = map(int, input().split())
print(math.floor((A*3+P)/2))
h, w = map(int, input().split())
p = [input() for i in range(h)]

th = []

for i in p:
    for n in range(2):
        th.append(i)

for x in th:
    print(x)


### FIXED CODE ###

c = input()
p = "aeiou"
if c in p:
    print("vowel")
else:
    print("consonant")
from math import pi
r = int(raw_input())
print '%f %f' % (pi * r ** 2, 2 * pi * r)

### FIXED CODE ###

from math import pi
r = float(raw_input())
print '%f %f' % (pi * r ** 2, 2 * pi * r)
x = map(int,input().split())
 
while str(x) != "0 0":    
    a=int(x).sort()
    for i in range(2):
        print(str(a[0]),str(a[1]))
    x = input()

### FIXED CODE ###

import sys
   
ff = sys.stdin
   
while True :
    a, b = map(int, ff.readline().split())
    if (a == 0) & (b == 0) :
        break
   
    if a < b : print(a, b)
    else : print(b, a)
N = int(input1())
As = list(map(int, input().split(' ')))

not_divisible = 0
for num_i, Ai in enumerate(As):
    for num_j, Aj in enumerate(As):
        if num_i==num_j:
            continue
        if Ai%Aj==0:
            break
    else:
        not_divisible += 1
print(not_divisible)

### FIXED CODE ###

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

max_a = max(a)
dp = [0] * (max_a + 1)

for i in a:
    for j in range(i, max_a+1, i):
        dp[j] += 1
        
print([dp[i] for i in a].count(1))
c =0

N = int(input())+1
S = tuple(input())


for i in range(1,N):
    for j in range(1,N):
        if i > j:
                continue
        elif S[i-1] == S[j-1]:
                continue
        for k in range(1,N):
            if j > k:
                continue
            elif S[i-1] == S[k-1] or S[j-1] == S[k-1]:
                continue
            elif j - i == k - j:
                continue
            else:
                c += 1
print(c)

### FIXED CODE ###

n = input()
print('Yes') if '7' in n else print('No')
n=input()

if n%2==0:
    print(n/2)
else:
    print(n//2+1)

### FIXED CODE ###

n=int(input())

if n%2==0:
    print(n//2)
else:
    print(n//2+1)
import math
import copy

# inputa = input().split()
# inputb = input().split()
# inputc = input().split()

# a = int(inputa[0])
# b = int(inputa[1])
# c = int(inputa[2])

# a = inputa[0]
# inputList = list(a)

# x = int(inputb[0])
# y = int(inputb[1])

a = 5
inputList=[]
for i in range(a):
    inputNum = input()
    inputList.append(inputNum)

inputList = [int(n) for n in inputList]

# b = [int(n) for n in inputb]
# c = [int(n) for n in inputc]

itemInfo = []
tmp = []

for i in range(a):
    tmp.append(int(math.floor(inputList[i]/10))*10)
    tmp.append(int(math.ceil(inputList[i]/10))*10)
    tmp.append(inputList[i]%10)
    itemInfo.append(copy.deepcopy(tmp))
    tmp.clear()

tmpList = sorted(itemInfo, key = lambda x:x[2])

flg = False
sum = 0
for i in range(len(tmpList)):
    if flg == False and tmpList[i][2] != 0:
        flg = True
        sum += tmpList[i][0] + tmpList[i][2]
    else:
        sum += tmpList[i][1]

print(sum)






### FIXED CODE ###

import math
import copy

# inputa = input().split()
# inputb = input().split()
# inputc = input().split()

# a = int(inputa[0])
# b = int(inputa[1])
# c = int(inputa[2])

# a = inputa[0]
# inputList = list(a)

# x = int(inputb[0])
# y = int(inputb[1])

a = 5
inputList=[]
for i in range(a):
    inputNum = input()
    inputList.append(inputNum)

inputList = [int(n) for n in inputList]

# b = [int(n) for n in inputb]
# c = [int(n) for n in inputc]

itemInfo = []
tmp = []

for i in range(a):
    tmp.append(int(math.floor(inputList[i]/10))*10)
    tmp.append(int(math.ceil(inputList[i]/10))*10)
    tmp.append(inputList[i]%10)
    itemInfo.append(copy.deepcopy(tmp))
    tmp.clear()

tmpList = sorted(itemInfo, key = lambda x:x[2])

flg = False
sum = 0
for i in range(len(tmpList)):
    if flg == False and tmpList[i][2] != 0:
        flg = True
        sum += tmpList[i][0] + tmpList[i][2]
    else:
        sum += tmpList[i][1]

print(sum)
# coding: utf-8
# Your code here!

import numpy as np

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

x = np.arange(N) + 1
c = np.ceil(np.log2(K / x)).astype(int)
c = c[np.where(c > 0)]
cumprod = np.cumprod([0.5] * int(c[0]+1))
print(2 * np.sum(cumprod[c]) / N + (N - len(c)) / N)

### FIXED CODE ###

# coding: utf-8
# Your code here!

import numpy as np

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

x = np.arange(N) + 1
c = np.ceil(np.log2(K / x)).astype(int)
c = c[np.where(c > 0)]
if len(c) == 0:
    print(1)
else:
    cumprod = np.cumprod([0.5] * int(c[0]+1))
    print(2 * np.sum(cumprod[c]) / N + (N - len(c)) / N)
a,b,c,d = input().split()
print('Yes' if a == b == c or b == c == d or a == b == d or a == c == d else 'No')


### FIXED CODE ###

a,b,c,d = input()
print('Yes' if a == b == c or b == c == d else 'No')
n=int(input())
l=list(map(int,input().split()))
if n%2==1:
  l=l[n-1::-2]+l[1::2]
  for i in range(5):
    print(l[i],end=" ")
else:
  l=l[n-1::-2]+l[::2]
  for i in range(5):
    print(l[i],end=" ")

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
if n%2==1:
  l=l[n-1::-2]+l[1::2]
  for i in range(n):
    print(l[i],end=" ")
else:
  l=l[n-1::-2]+l[::2]
  for i in range(n):
    print(l[i],end=" ")
a,b,c,d,e=map(int,input().split())

if a=0:
    print('1')
if b=0:
    print('2')
if c=0:
    print('3')
if d=0:
    print('4')
if e=0:
    print('5')





### FIXED CODE ###

a,b,c,d,e=map(int,input().split())

if a==0:
    print('1')
if b==0:
    print('2')
if c==0:
    print('3')
if d==0:
    print('4')
if e==0:
    print('5')
s=input()
if s=="SSS":
  print(0)
else if s=="RRS" or s= "SRR":
  print(2)
else if s= "RRR":
  print(3)
else:
  print(1)

### FIXED CODE ###

s=input()
if s=="SSS":
  print(0)
elif s=="RRS" or s== "SRR":
  print(2)
elif s== "RRR":
  print(3)
else:
  print(1)
s=input()
n=len(s)+1
l=[0]*n
r=[0]*n
for i in range(n-1):
    if S[i]=='<': 
      l[i+1]=l[i]+1
    if S[n-2-i]=='>': 
      r[n-2-i]=r[n-1-i]+1
ans=0
for i in range(N):
  ans+=max(l[i],r[i])
print(ans)


### FIXED CODE ###

s=input()
n=len(s)+1
l=[0]*n
r=[0]*n
for i in range(n-1):
    if s[i]=='<': 
      l[i+1]=l[i]+1
    if s[n-2-i]=='>': 
      r[n-2-i]=r[n-1-i]+1
ans=0
for i in range(n):
  ans+=max(l[i],r[i])
print(ans)
import math
A, B = map(int, input().split())
print(math.floor(A * B))

### FIXED CODE ###

from math import floor
from decimal import Decimal
a, b = map(Decimal, input().split())
print(floor(a*b))
n = int(input())
m = [i for i in range(1,n+1)]
p = list(map(int,input().split()))
cnt = 0
for i in m:
    if p[i-1] == i:
        p[i-1] = p[i]
        p[i] = i
        cnt += 1
    
print(cnt)

### FIXED CODE ###

n = int(input())
m = [i for i in range(1,n)]
p = list(map(int,input().split()))
cnt = 0
for i in m:
    if p[i-1] == i:
        p[i-1] = p[i]
        p[i] = i
        cnt += 1

if p[-1] == n:
    cnt += 1
print(cnt)
l, r = map(int, input().split())
l, r = l%2019, r%2019
mi = 9999
if r*(r-1)<2019:
    print(l*(l+1))
elif r==0 or l==0:
    print(0)
else:
    for i in range(l, r-1):
        for j in range(i+1, r):
            if (i/3).is_integer() and (j/673).is_integer():
                print((i/3)*((i/3)+1))
            elif (i/673).is_integer() and (j/3).is_integer():
                print((i/673)*((i/673)+1))
            else:
                mi = min(mi, (i*j)%2019)
    print(mi)  

### FIXED CODE ###

n, a, b = map(int, input().split())
print(min(a*n, b))
k = int(input())
s = input()
if int(len(s)) <= k:
  	print(str(s))
else:
  	print(((str(s))[0:k])

### FIXED CODE ###

k = int(input())
s = input()
if int(len(s)) <= k:
  	print(str(s))
else:
  	print(((str(s))[0:k]) + "...")
'''
https://atcoder.jp/contests/abc150/tasks/abc150_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    a = list(map(int, input().split()))
    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    def gcd_group(arr):
        g = gcd(arr[0], arr[1])
        for i in range(2, len(arr)):
            g = gcd(g, arr[i])
        return g
    
    def lcm(a, b):
        g = gcd(a, b)
        return (a*b)//g
    
    def lcm_group(arr):
        l = lcm(arr[0], arr[1])
        for i in range(2, len(arr)):
            l = lcm(l, arr[i])
        return l
    
    lcm = lcm_group(a)
    semi_lcm = lcm // 2
    if m >= semi_lcm:
        print((m-semi_lcm)//lcm + 1)
    else:
        print(0)


if __name__ == '__main__':
    main()

### FIXED CODE ###

'''
https://atcoder.jp/contests/abc150/tasks/abc150_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

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

    if len(a) == 1:
        if m >= a[0]//2:
            print((m-a[0]//2) // a[0] + 1)
        else:
            print(0)
        exit()

    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    def gcd_group(arr):
        g = gcd(arr[0], arr[1])
        for i in range(2, len(arr)):
            g = gcd(g, arr[i])
        return g
    
    def lcm(a, b):
        g = gcd(a, b)
        return (a*b)//g
    
    def lcm_group(arr):
        l = lcm(arr[0], arr[1])
        for i in range(2, len(arr)):
            l = lcm(l, arr[i])
        return l
    g = gcd_group(a)
    for i in a:
        if (i//g)%2 == 0:
            print(0)
            exit()
    lcm = lcm_group(a)
    semi_lcm = lcm // 2
    if m >= semi_lcm:
        print((m-semi_lcm)//lcm + 1)
    else:
        print(0)


if __name__ == '__main__':
    main()
n, m = map(int, input().split())
a=list(map(int, input().split()))
s=[0]*(n+1)
for i in range(1, n+1):
    s[i]=s[i-1]+a[i-1]
dic={}
for i in range(n+1):
    tmp=s[i]%m
    if tmp in dic.keys():
        dic[tmp]+=1
    else:
        dic[tmp]=1
ans=0
for i in dic.values():
    ans+=i*(i-1)//2
print(ans)
n, m = map(int, input().split())
a=list(map(int, input().split()))
s=[0]*(n+1)
for i in range(1, n+1):
    s[i]=s[i-1]+a[i-1]
dic={}
for i in range(n+1):
    tmp=s[i]%m
    if tmp in dic.keys():
        dic[tmp]+=1
    else:
        dic[tmp]=1
ans=0
for i in dic.values():
    ans+=i*(i-1)//2
print(ans)

### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    a=list(map(int, input().split()))
    s=[0]*(n+1)
    for i in range(1, n+1):
        s[i]=s[i-1]+a[i-1]
    dic={}
    for i in range(n+1):
        tmp=s[i]%m
        if tmp in dic.keys():
            dic[tmp]+=1
        else:
            dic[tmp]=1
    ans=0
    for i in dic.values():
        ans+=i*(i-1)//2
    print(ans)
if __name__ == '__main__':
    main()
n,m = map(int,input().split())
P = list(map(int,input().split()))
R = [list(map(int,input().split())) for i in range(m)]
U = [-1]*n
def root(x):
    if x == U[x-1]:
        return x
    if U[x-1] == -1:
        return x
    return root(U[x-1])
for r in R:
    if U[r[0]-1]==-1:
        if U[r[1]-1]==-1:
            U[r[0]-1] = r[0]
            U[r[1]-1] = r[0]
        else:
            U[r[0]-1] = U[r[1]-1]
    else:
        if U[r[1]-1]==-1:
            U[r[1]-1] = U[r[0]-1]
        else:
            U[root(r[1])-1] = U[r[0]-1]
count = 0
for i in range(n):
    if root(P[i]) == root(i+1) and U[i] != -1:
        count += 1
    elif U[i] == -1 and P[i]-1 == i:
        count += 1
print(count)

### FIXED CODE ###

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 same(self, x, y):
        return self.find(x) == self.find(y)

n,m = map(int,input().split())
Permutation = list(map(int,input().split()))
Replace = [list(map(int,input().split())) for i in range(m)]

uf = UnionFind(n+1)
count = 0

for i in range(m):
    uf.union(Replace[i][0],Replace[i][1])

for i in range(1,n+1):
    if uf.same(Permutation[i-1],i):
        count += 1

print(count)
N,K=list(map(int,input().strip().split(' ')))
A=[]
for _ in range(N):
    A+=[list(map(int,input().strip().split(' ')))]
dic={}
MOD=10**9+7
def findout(i,j,k):
    
    if k==1:
        if A[i][j]==1:
            return 1
        else:
            return 0
    if (i,j,k) in dic:
        return dic[(i,j,k)]
    N=len(A)
    a1=k//2
    a2=k-a1
    
    ans=0
    for node in range(N):
        ans+=(findout(i,node,a1)*findout(node,j,a2))%MOD
    dic[(i,j,k)]=ans
    return ans
ans=0
for i in range(4):
    for j in range(4):
        ans+=findout(i,j,K)
        ans%=MOD
print(ans)

### FIXED CODE ###

N,K=list(map(int,input().strip().split(' ')))
A=[]
for _ in range(N):
    A+=[list(map(int,input().strip().split(' ')))]
dic={}
MOD=10**9+7
power=1
while 2**power<=K:
    power+=1

dp=[[[0 for j in range(N)] for i in range(N)] for p in range(power+1) ]
for p in range(0,power+1):
    
    if p==0:
        for i in range(N):
            for j in range(N):
                if A[i][j]==1:
                    dp[p][i][j]=1
    else:
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    dp[p][i][j]+=(dp[p-1][i][k]*dp[p-1][k][j])%MOD
                    dp[p][i][j]%=MOD

    
rep=bin(K)[2:][::-1]
final_ans=[[0 for i in range(N)] for j in range(N)]
need=[]
for i in range(len(rep)):
    if rep[i]=="1":
        need+=[i]

final=[[dp[need[0]][i][j] for j in range(N)] for i in range(N)]
for i in range(1,len(need)):
    ##start*dp[need[i]]
    temp_ans=[[0 for i in range(N)] for j in range(N)]
    for x in range(N):
        for y in range(N):
            temp=0
            for z in range(N):
                temp+=final[x][z]*dp[need[i]][z][y]
                temp%=MOD
            temp_ans[x][y]=temp
    final=[[temp_ans[i][j] for j in range(N)] for i in range(N)]
            
ans=0
for i in range(N):
    for j in range(N):
        ans+=final[i][j]
        ans%=MOD
print(ans)
import math
a,b,x = map(int,input().split())
if x >= (b*a**2)/2:
    print(90-math.degrees(math.atan(a**3/(2*(b*a**2-x)))))
else:
    print(90-math.degrees(math.atan(2*x/(a*b**2))))

### FIXED CODE ###

import math
a,b,x = map(int,input().split())
if b*a**2 == x:
    print("0")
elif x >= (b*a**2)/2:
    print(90-math.degrees(math.atan(a**3/(2*(b*a**2-x)))))
else:
    print(90-math.degrees(math.atan(2*x/(a*b**2))))
n = int(input())
l = list(map(int, input().split()))
l2 = l.copy()

l.sort(reverse=True)
l2.sort()
for num in range(n):
	if(l[0] > sum(l2[:n])):
  		print("Yes")
		break
print("No")


### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
 
l.sort(reverse=True)
if(l[0] < sum(l[1:n])):
  print("Yes")
else:
  print("No")
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
q, h, s, d = map(int, sys.stdin.readline().rstrip().split())
N = I()
D = d
qh = min(2*q, h)
S = min(2*qh, s)
x = min(2*S, D)
if N%2 == 0:
    print(N//2*x)
else:
    print(N//2*x + S)

### FIXED CODE ###

import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
q, h, s, d = map(int, sys.stdin.readline().rstrip().split())
N = I()
D = d
qh = min(2*q, h)
S = min(2*qh, s)
x = min(2*S, D)
if N%2 == 0:
    print(N//2*x)
else:
    print(N//2*x + S)
a=list(map(lambda x:x,input(),split()))
if(a[1]>a[0]):
  print(a[0]*int(a[1]))
else:
  print(a[1]*int(a[0]))

### FIXED CODE ###

a=list(map(lambda x:x,input().split()))
if(a[0]==a[1]):
       print("Yes")
else:
       print("No")
n, k = map(int, input().split())
a = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x:-x[1])
 
ans = 0
s = set()
q = []
 
for i in range(k):
    ans += a[i][1]
    if a[i][0] in s:
        q.append(a[i][1])
    s.add(a[i][0])
 
ans += len(s)**2
k1 = k
ans1 = ans
 
#はじめ0~k-1までの和がansなので、k~n-1でチェック
while k1 < n and q:
    if a[k1][0] not in s:
        ans1 = ans1+a[k1][1]-q.pop()-len(s)**2+(len(s)+1)**2
        ans = max(ans, ans1)
        s.add(a[k1][0])
    k1 += 1
 
print(ans)

### FIXED CODE ###

lst = list(map(int, input().split()))
lst.sort()
print(int(lst[0]*lst[1]*1/2))
a=int(input())
if a%7==1:
    print("fri")
if a%7==2:
    print("sat")
if a%7==3:
    print("sun")
if a%7==4:
    print("mon")
if a%7==5:
    print("tue")
if a%7==6:
    print("wed")
if a%==7:
    print("thu")


### FIXED CODE ###

a=int(input())
if a%7==1:
    print("fri")
if a%7==2:
    print("sat")
if a%7==3:
    print("sun")
if a%7==4:
    print("mon")
if a%7==5:
    print("tue")
if a%7==6:
    print("wed")
if a%7==0:
    print("thu")
#!/usr/bin/env python3
import sys
from itertools import accumulate
INF = float("inf")


def solve(N: int, C: int, s: "List[int]", t: "List[int]", c: "List[int]"):
    # いもす法
    seq = [0]*(2*10**5)
    for sv, tv, cv in zip(s, t, c):
        seq[2*sv-1] += 1
        seq[2*tv] -= 1
    acc = list(accumulate(seq))
    # print(seq)
    # print(acc)
    print(max(acc))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    s = [int()] * (N)  # type: "List[int]"
    t = [int()] * (N)  # type: "List[int]"
    c = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        s[i] = int(next(tokens))
        t[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, C, s, t, c)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from itertools import accumulate
INF = float("inf")


def solve(N: int, C: int, s: "List[int]", t: "List[int]", c: "List[int]"):
    seq = [0]*(3*10**5)
    # チャンネルを切り替えない場合、0.5秒のラグが発生しない。
    # 同じチャンネルでしりとあたまがいっしょなら、ひとつの番組にしておく
    c, s, t = zip(*sorted(sorted(zip(c, s, t), key=lambda x: x[1])))
    # いもす法
    # seq = [0]*(40)
    pre_s, pre_t, pre_c = -1, -1, -1
    for sv, tv, cv in zip(s, t, c):
        if pre_c == cv and pre_t == sv:
            seq[2*pre_t] += 1
            seq[2*tv] -= 1
        else:
            seq[2*sv-1] += 1
            seq[2*tv] -= 1
        pre_s, pre_t, pre_c = sv, tv, cv
    acc = list(accumulate(seq))
    # print(seq)
    # print(acc)
    print(max(acc))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    s = [int()] * (N)  # type: "List[int]"
    t = [int()] * (N)  # type: "List[int]"
    c = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        s[i] = int(next(tokens))
        t[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, C, s, t, c)


if __name__ == '__main__':
    main()
n, k, x, y = map(int, input().split())

if n <= k:
    print(n * x)
else:
    print(k * x + (n - k) * y)

### FIXED CODE ###

N = int(input())   
K = int(input())   
X = int(input())    
Y = int(input())    

if N <= K:
    print(N * X)
else:
    print(K * X + (N - K) * Y)
l, r = map(int, input().split())
mod = 2019
if r - l > 3000:
  print(0)
else:
  ans = mod
  for i in range(l, r + 1):
    for j in range(r, l, -1):
      #print(str(i) + ' ' + str(j))
      if j <= i: break
      ans = min(ans, (i * j) % mod)
print(ans)
      

### FIXED CODE ###

l, r = map(int, input().split())
mod = 2019
if r - l > 3000:
  print(0)
else:
  ans = mod
  for i in range(l, r + 1):
    for j in range(r, l, -1):
      #print(str(i) + ' ' + str(j))
      if j <= i: break
      ans = min(ans, (i * j) % mod)
  print(ans)
n = int(input())
A = list(map(int, input().split()))

a=0
result=0

for i in range(n-1):
  if A[i] > A[i+1]:
    a = A[i] - A[i+1]
    result += a
    
print(result)

### FIXED CODE ###

n = int(input())

SUM = sum(list(map(int, str(n))))

if SUM % 9 == 0:
  print("Yes")
else:
  print("No")
S, W = map(int, input().split())
if S =< W:
    print("unsafe")
else:
    print("safe")


### FIXED CODE ###

S, W = map(int, input().split())
if S <= W:
    print("unsafe")
else:
    print("safe")
S=input()
ans=0
for i in S:
    if i='+':ans+=1
    else: i-=1

### FIXED CODE ###

S=input()
ans=0
for i in S:
    if i=='+':ans+=1
    else: ans-=1
print(ans)
N = int(input())
cs = [0]*N
for i in range(1,130):
    for j in range(1,130):
        for k in range(1,130):
            temp = i**2 + j**2 + k**2 + i*j + j*k + k*i
            if temp =< N and temp > 0:
                cs[temp-1] += 1
for i in range(N):
    print(cs[i])


### FIXED CODE ###

L,R,d = map(int,input().split())
c = 0
for i in range(L,R+1):
  if i % d ==0:
    c+=1
print(c)
s = input()
t = input()
for i in range(len(s)-1):
  if s[i]!=t[i]:
    f =1
if f==1:
  print("No")
else:
  print("yes")

### FIXED CODE ###

s =input()
t =input()
f=0
for i in range(len(s)):
	if s[i]!=t[i]:
		f=1
		break
if f==1:
	print("No")
else:
	print("Yes")