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

N,Q = map(int,input().split())
S = input()
AC = []

for i in range(N-1):
  if S[i]+S[i+1] == "AC":
    AC.append(i+1.5)

for j in range(Q):
  l,r = map(int,input().split())
  cnt = 0
  for k in AC:
    if l < k < r:
      cnt += 1
    if r < k:
      break
  print(cnt)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
t = [0]*(N+1)

for i in range(N):
  t[i+1] = t[i] + (1 if S[i:i+2] == "AC" else 0)
  
for j in range(Q):
  l,r = map(int,input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    sl = [ list(input()) for _ in range(n) ]
    ans = 0

    
    for i in sl:
        i.sort() #sort() methodは元を変える
    
    st = tuple(sl)
    
    for i in range(len(st)-1):
        for j in range(i+1,len(st)):
            if st[i] == st[j]:
                ans += 1

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

A ={}
c = 0
for i in range(int(input())):
    a = str(sorted(input()))
    if a in A:
        A[a] += 1
        c += A[a]
    else:
        A[a] = 0
print(c)
### BUGGY CODE ###

import math
N = int(input())
count=0
g = 0
y= 0
for i in range(1,N+1):
  y=int(N/i)
  g=y*(y+1)*i/2
  count+=g

print(int(count))

### FIXED CODE ###

N = int(input())
count=0
g = 0
y= 0
for i in range(1,N+1):
  y=int(N/i)
  g=y*(y+1)*i/2
  count+=g

print(int(count))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(100000)


def k(x):
    if x < 2:
        return 1
    return x * k(x - 1)


n, m = map(int, input().split())
w = 10 ** 9 + 7
if n + 1 == m or m + 1 == n:
    print(k(n) * k(m) % w)
elif n == m:
    print(2 * k(n) ** 2 % w)
else:
    print(0)


### FIXED CODE ###

import math

n, m = map(int, input().split())
w = 10 ** 9 + 7
if n + 1 == m or m + 1 == n:
    print(math.factorial(min(n, m)) ** 2 * max(n, m) % w)
elif n == m:
    print(2 * math.factorial(n) ** 2 % w)
else:
    print(0)
### BUGGY CODE ###

import sys
def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b

def check_t(num):
    i = 1
    while(True):
        if num < 2**i:
            return 2**i
        else:
            i += 1


from collections import defaultdict
n = getN()
nums = getlist()
numhash = defaultdict(int)
for i in nums:
    numhash[i] += 1
ans = 0
for num in sorted(numhash.keys(), key=lambda x: -x):
    while(numhash[num] != 0):
        target  = (check_t(num)) - num
        if numhash[target]:
            if target == num:
                if numhash[target] >= 2:
                    ans += 1
                    numhash[target] -= 2
                else:
                    numhash[num] = 0
            else:
                if numhash[target] >= 1:
                    ans += 1
                    numhash[target] -= 1
                    numhash[num] -= 1
                else:
                    numhash[num] = 0
        else:
            numhash[num] = 0


print(ans)


### FIXED CODE ###

import sys
import math
def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b

def check_t(num):
    t = math.log(num,2)
    return 2**(int(t)+1)



from collections import defaultdict
n = getN()
nums = getlist()
numhash = defaultdict(int)
for i in nums:
    numhash[i] += 1
ans = 0
for num in sorted(numhash.keys(), key=lambda x: -x):
    while(numhash[num] != 0):
        target = (check_t(num)) - num
        if numhash[target]:

            if target == num:
                if numhash[target] >= 2:
                    ans += 1
                    numhash[target] -= 2
                else:
                    numhash[num] = 0
            else:
                if numhash[target] >= 1:
                    ans += 1
                    numhash[target] -= 1
                    numhash[num] -= 1
                else:
                    numhash[num] = 0
        else:
            numhash[num] = 0


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

H, W = map(int, input().split())
S = ""
for i in range(H):
    S += input()

vert = [0] * (H*W)
horz = [0] * (H*W)

for i in range(H*W):
    if S[i] == '.':
        if i - W >= 0:
            if S[i - W] == '.':
                vert[i] = vert[i - W]
                continue
        j = i
        while True:
            if j >= H * W:
                break
            if S[j] == '.':
                vert[i] += 1
            else:
                break
            j += W

for i in range(H*W):
    if S[i] == '.':
        if i % W > 0:
            if S[i - 1] == '.':
                horz[i] = horz[i - 1]
                continue
        j = i
        while True:
            if S[j] == '.':
                horz[i] += 1
            else:
                break
            j += 1
            if j % W == 0:
                break

light = [0] * (H*W)
for i in range(H * W):
    light[i] = horz[i] + vert[i]
print(max(light) - 1)


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        grid.append(input().rstrip('\n'))

    L = [[0] * W for _ in range(H)]
    R = [[0] * W for _ in range(H)]
    U = [[0] * W for _ in range(H)]
    D = [[0] * W for _ in range(H)]
    for h in range(H):
        for w in range(1, W):
            if grid[h][w-1] == '.' and grid[h][w] == '.':
                L[h][w] = L[h][w-1] + 1
    for h in range(H):
        for w in range(W-2, -1, -1):
            if grid[h][w] == '.' and grid[h][w+1] == '.':
                R[h][w] = R[h][w+1] + 1
    for w in range(W):
        for h in range(1, H):
            if grid[h][w] == '.' and grid[h-1][w] == '.':
                U[h][w] = U[h-1][w] + 1
    for w in range(W):
        for h in range(H-2, -1, -1):
            if grid[h][w] == '.' and grid[h+1][w] == '.':
                D[h][w] = D[h+1][w] + 1

    ans = 1
    for h in range(H):
        for w in range(W):
            ans = max(ans, L[h][w] + R[h][w] + U[h][w] + D[h][w] + 1)
    print(ans)


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

N = int(input())
P = list(map(int, input().split()))
cnt = 0

for i in reversed(range(len(P))):
  for j in reversed(range(i)):
    if P[i] <= P[j]:
      if j == 0:
        cnt += 1
      pass
    else:
      break

cnt += 1
print(cnt)


### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))

'''
参考
https://cocoinit23.com/abc152/
すべての(i, j)を調べていると制限時間を超過してしまう。
listの2つ目の要素(index=1)から順に見ていって、最小値が更新されたら解をカウントアップする。
ただし、解の最小値は常に1となるので、解の初期値は1にしておくこと。
'''
ans = 1
min_p = P[0]

for i in range(1, N):
    if P[i] <= min_p:
        min_p = P[i]
        ans += 1

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

# -*- coding: utf-8 -*-

def main():
    n = int(input())
    d = dict()

    for i in range(n):
        s = input()
        if s in d.keys():
            d[s] += 1
        else:
            d[s] = 1

    m_list = [kv[0] for kv in d.items() if kv[1] == max(d.values())]
    m_list = sorted(m_list)
    print('\n'.join(m_list))

if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-

def main():
    n = int(input())
    d = dict()

    for i in range(n):
        s = input()
        if s in d.keys():
            d[s] += 1
        else:
            d[s] = 1

    d_m = max(d.values())
    m_list = [kv[0] for kv in d.items() if kv[1] == d_m]
    m_list = sorted(m_list)
    print('\n'.join(m_list))

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

import numpy as np

N = int(input())
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

D = np.array([len(make_divisors(n)) for n in range(1,N+1)])
D1 = np.arange(1,N+1)
print(sum(D*D1))

### FIXED CODE ###

N = int(input())

ans = 0
for j in range(1,N+1):
    num = int(N/j)
    ans += num*(num+1)/2*j
print(int(ans))
### BUGGY CODE ###

K, N  = map(int,input().split())
List = list(map(int,input().split()))
d = []
for i in range(N):
  for j in range(N):
    x = min(abs(List[i]-List[j]), K-abs(List[i]-List[j]))
    d.append(x)
result = K - int(max(d))
print(result)

### FIXED CODE ###

K, N  = map(int,input().split())
List = list(map(int,input().split()))
d = []
for i in range(1,N):
  x = min(abs(List[i]-List[i-1]), K-abs(List[i]-List[i-1]))
  d.append(x)
d.append(min(abs(List[N-1]-List[0]), K-abs(List[N-1]-List[0])))
result = K - int(max(d))
print(result)
### BUGGY CODE ###

def candy_distribution(N: int, M: int, A: list)->int:
    S = [0] * (N+1)
    for i, a in enumerate(A):
        S[i+1] = S[i] + a

    count = 0
    for l in range(1, N+1):
        for r in range(l, N+1):
            if (S[r] - S[l-1]) % M == 0:
                # print('S({}, {}) = {}'.format(l, r, S[r] - S[l-1]))
                count += 1

    return count


if __name__ == "__main__":
    N, M = map(int, input().split())
    A = [int(s) for s in input().split()]
    ans = candy_distribution(N, M, A)
    print(ans)


### FIXED CODE ###

def candy_distribution(N: int, M: int, A: list)->int:
    S = 0
    remainders = {}
    remainders[0] = 1
    for a in A:
        S = (S + a) % M
        if S not in remainders:
            remainders[S] = 0
        remainders[S] += 1

    count = sum(r*(r-1)//2 for r in remainders.values())
    # for l in range(1, N+1):
    #     for r in range(l, N+1):
    #         if (S[r] - S[l-1]) % M == 0:
    #             # print('S({}, {}) = {}'.format(l, r, S[r] - S[l-1]))
    #             count += 1

    return count


if __name__ == "__main__":
    N, M = map(int, input().split())
    A = [int(s) for s in input().split()]
    ans = candy_distribution(N, M, A)
    print(ans)
### BUGGY CODE ###

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

k=int(input())
ans=0
for a in range(1,k+1):
    for b in range(1,k+1):
        temp=gcd(a,b)
        for c in range(1,k+1):
            ans+=gcd(temp,c)
print(ans)

### FIXED CODE ###

from math import gcd

k=int(input())
ans=0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans+=gcd(a,gcd(b,c))
print(ans)
### BUGGY CODE ###

n=int(input())
x= list(range(-10000, 10000, 1))
#print(x)
a = 100
b = 100
for i in x:
    for j in x:
        if i**5-j**5 == n:
            print(i, end=" ")
            print(j)
            exit()

### FIXED CODE ###

n=int(input())
x= list(range(-1000, 1000, 1))
#print(x)
a = 100
b = 100
for i in x:
    for j in x:
        if i**5-j**5 == n:
            print(i, end=" ")
            print(j)
            exit()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def solve(N: int, a: "List[int]"):
    N1 = N + 1
    dpmin = [-1] * N1 ** 2
    dpmax = [-1] * N1 ** 2
    for i in range(N1):
        dpmin[0 * N1 + i] = dpmax[0 * N1 + i] = 0
    for i in range(N):
        dpmin[1 * N1 + i] = -a[i]
        dpmax[1 * N1 + i] = a[i]
    for k in range(2, N1):
        for i in range(N - k + 1):
            dpmin[k * N1 + i] = min(
                -a[i] + dpmax[(k - 1) * N1 + i + 1],
                -a[i + k - 1] + dpmax[(k - 1) * N1 + i],
            )
            r = -1
            dpmax[k * N1 + i] = max(
                a[i] + dpmin[(k - 1) * N1 + i + 1],
                a[i + k - 1] + dpmin[(k - 1) * N1 + i],
            )
    return dpmax[N * N1]


def main():
    N = int(readline())  # type: int
    a = [int(x) for x in readline().split()]  # type: "List[int]"
    print(solve(N, a))


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def solve(N: int, a: "List[int]"):
    N1 = N + 1
    dpmin = [-1] * N1 ** 2
    dpmax = [-1] * N1 ** 2
    for i in range(N1):
        dpmin[0 * N1 + i] = dpmax[0 * N1 + i] = 0
    for i in range(N):
        dpmin[1 * N1 + i] = -a[i]
        dpmax[1 * N1 + i] = a[i]
    for k in range(2, N1):
        for i in range(N - k + 1):
            dpmin[k * N1 + i] = min(
                -a[i] + dpmax[(k - 1) * N1 + i + 1],
                -a[i + k - 1] + dpmax[(k - 1) * N1 + i],
            )
            r = -1
            dpmax[k * N1 + i] = max(
                a[i] + dpmin[(k - 1) * N1 + i + 1],
                a[i + k - 1] + dpmin[(k - 1) * N1 + i],
            )
    return dpmax[N * N1]


def main():
    N = int(readline())  # type: int
    a = [int(x) for x in readline().split()]  # type: "List[int]"
    print(solve(N, a))


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

S = input()
T = input()
LS = len(S)
LT = len(T)

dp = [0] * (LT+1)
dp[0] = -1
valid = True

for i in range(1,LT+1):
    t = T[i-1]
    p = (dp[i-1] + 1) % LS
    f = False  # find or not
    for j in range(p, LS):
        if S[j] == t:
            dp[i] = dp[i-1] + j - p + 1
            f = True
            break
    if f:
        continue
    for j in range(p):
        if S[j] == t:
            dp[i] = dp[i-1] + (LS - p) + j + 1
            f = True
            break
    if f:
        continue
    valid = False
    break
    
print(dp[-1] + 1 if valid else -1)


### FIXED CODE ###

from bisect import bisect
S = input()
T = input()
LS = len(S)
LT = len(T)

H = {chr(i): [] for i in range(ord('a'), ord('z')+1)}
for i, s in enumerate(S):
    H[s].append(i)

dp = [0] * (LT+1)
dp[0] = -1
valid = True

for i in range(1,LT+1):
    t = T[i-1]
    p = dp[i-1] % LS if i > 1 else -1
    if len(H[t]) == 0:
        valid = False
        break
    q = bisect(H[t], p)
    if q == len(H[t]):
        dp[i] = dp[i-1] + LS - p + H[t][0]
    else:
        dp[i] = dp[i-1] + H[t][q] - p

print(dp[-1] + 1 if valid else -1)
### BUGGY CODE ###

k,s=map(int,input().split())
ans=0
for x in range(k+1):
    for y in range(k+1):
        z=s-x-y
        if x+y+z==s and 0<=z<=k:
            ans+=1
print(ans)



### FIXED CODE ###

# ABC051 B - Sum of Three Integers
K,S = map(int,input().split())
ans = 0
for i in range(0,K+1):
    for j in range(0,K+1):
        k = S-i-j
        if 0<=k<=K:
                ans += 1
print(ans)
### BUGGY CODE ###

#!python3

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]

    AB.sort(key=lambda a: (a[0]/a[1], a[0]), reverse=True)

    S = []
    for a, b in AB:
        n, m = divmod(H, a)
        i = 1
        while n >= i:
            S.append((a*i, b*i))
            n -= i
            i <<= 1
        if m:
            n += 1
        if n:
            S.append((a*n, b*n))

    N2 = len(S)
    def ubound(b, a, i):
        for j in range(i, N2):
            aj, bj = S[j]
            if a + aj >= H:
                return (b+bj, b + (H-a) * bj / aj)
            a += aj
            b += bj

        return (inf, inf)

    q = []
    u0, u1 = ubound(0, 0, 0)

    inf = float("inf")
    heappush(q, (u1, u0, 0, 0, 0))
    um = u0
    #print(AB)
    #print(H, S)
    while q:
        #print(q)
        uq0, uq1, aq, bq, i = heappop(q)

        if uq0 >= um:
            break

        if i >= N2: continue

        ai, bi = S[i]
        if aq + ai < H:
            heappush(q, (uq0, uq1, aq + ai, bq + bi, i + 1))

        u0, u1 = ubound(bq, aq, i + 1)
        if u1 <= um:
            if u0 < um:
                um = u0
            heappush(q, (u1, u0, aq, bq, i + 1))

    print(um)



if __name__ == "__main__":
    resolve()



### FIXED CODE ###

#!python3
import sys
sys.setrecursionlimit(1000000)

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]
    inf = float("inf")
    AB.sort(key=lambda a: (a[0]/a[1], -a[0]), reverse=True)

    def memo(f):
        cache = {}
        def wrapper(*a):
            if a in cache:
                return cache[a]
            b = f(*a)
            cache[a] = b

            return b

        return wrapper

    @memo
    def calc(h):
        if h <= 0: return 0

        bi = inf
        for a, b in AB:
            bj = b + calc(h - a)
            if bi > bj:
                bi = bj
            else:
                break
        return bi

    print(calc(H))



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

MOD = 10**9 + 7
memo = None


def rec(S, k, total):
    if k == len(S)//3:
        # print(total)
        fixed_total = total + 5 if k % 2 == 0 else total - 5
        # fixed_total = abs(total) + 5
        memo[k][total % 13] = int((fixed_total) % 13 == 0)
        return int((fixed_total) % 13 == 0)

    if memo[k][total % 13] is not None:
        return memo[k][total % 13]

    s = S[k*3:k*3+3]
    d1 = [str(i) for i in range(10)] if s[0] == '?' else [s[0]]
    d2 = [str(i) for i in range(10)] if s[1] == '?' else [s[1]]
    d3 = [str(i) for i in range(10)] if s[2] == '?' else [s[2]]
    ret = 0

    for i1 in d1:
        for i2 in d2:
            for i3 in d3:
                num = int(i1 + i2 + i3)
                if k % 2 == 0:
                    ret += rec(S, k+1, total + num)
                else:
                    ret += rec(S, k+1, total - num)

    memo[k][total % 13] = ret
    return ret

S = input()

if len(S) % 3 == 1:
    S = '00' + S
elif len(S) % 3 == 2:
    S = '0' + S

L = (len(S) // 3)
dp = [[0 for i in range(14)] for j in range(L + 1)]
# print(rec(S, 0, 0) % MOD)
# print(memo)

dp[0][0] = 1

for k in range(L):
    for m in range(13):
        s = S[k*3:k*3+3]
        d1 = [str(i) for i in range(10)] if s[0] == '?' else [s[0]]
        d2 = [str(i) for i in range(10)] if s[1] == '?' else [s[1]]
        d3 = [str(i) for i in range(10)] if s[2] == '?' else [s[2]]

        for i1 in d1:
            for i2 in d2:
                for i3 in d3:
                    num = int(i1 + i2 + i3)
                    dp[k + 1][(13 + num - m) % 13] += dp[k][m]

        for i in range(13):
            dp[k][m] %= MOD

print(dp[L][5] % MOD)

# L = len(S)
# memo = [[0 for i in range(14)] for j in range(L + 1)]
# dp = [[0 for i in range(14)] for j in range(L + 1)]
# # print(rec(S, 0, 0) % MOD)
# # print(memo)

# dp[0][0] = 1

# for k in range(L):
#     for m in range(13):
#         if S[k] == '?':
#             for i in range(10):
#                 print('k', k, 'm', m, '(m * 10 + i)', (m * 10 + i))
#                 dp[k + 1][(m * 10 + i) % 13] += dp[k][m]
#         else:
#             dp[k + 1][(m * 10 + int(S[k])) % 13] += dp[k][m]

# print(dp[L][5] % MOD)


### FIXED CODE ###

MOD = 10**9 + 7

S = input()
L = len(S)
memo = [[0 for i in range(14)] for j in range(L + 1)]
dp = [[0 for i in range(14)] for j in range(L + 1)]

dp[0][0] = 1

for k in range(L):
    for m in range(13):
        if S[k] == '?':
            for i in range(10):
                dp[k + 1][(m * 10 + i) % 13] += dp[k][m]
        else:
            dp[k + 1][(m * 10 + int(S[k])) % 13] += dp[k][m]

        for i in range(13):
            dp[k+1][i] %= MOD

print(dp[L][5])
### BUGGY CODE ###

n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(m)]
ikeruheya = [[] for i in range(n)]
ans = [0]*(n+1)
#check = [0]*n
#check[0]=1
ans[0]=-1
ans[1]=1
for i in range(m):
    ikeruheya[a[i][0]-1].append(a[i][1])
    ikeruheya[a[i][1]-1].append(a[i][0])

    
next=[1]
count = 1
while count <= n and len(next) != 0:
    imaheya = next.pop(0)
    j = 0
    while j < len(ikeruheya[imaheya-1]) and count <= n:
        if ans[ikeruheya[imaheya-1][j]]==0:
            ans[ikeruheya[imaheya-1][j]]= imaheya 
            #check[ikeruheya[imaheya-1][j]-1] = 1
            next.append(ikeruheya[imaheya-1][j])
            count += 1
            j+=1
        else:
            j+=1
    
            
print("Yes")
for i in range(2, n+1):
    print(ans[i])


    
    


### FIXED CODE ###

from collections import deque
n,m = map(int,input().split())
a=[list(map(int, input().split())) for i in range(m)]
b=[[] for j in range(n)] 

michi=[-1]*(n)
michi[0]=0
heya=[]


for i in range(m):
    b[a[i][0]-1].append(a[i][1])
    b[a[i][1]-1].append(a[i][0])



heya.append(1)


while len(heya):
    now=heya.pop(0)-1
    
    for i in range(len(b[now])):
        if michi[b[now][i]-1] == -1:
            heya.append(b[now][i])
            michi[b[now][i]-1] = now+1
print("Yes")
for i in range(1,n):
    print(michi[i])
### BUGGY CODE ###

n,x=map(int,input().split())
line=list(map(int,input().split()))
Sum=[0]
sum=0
for i in range(n):
  sum+=line.pop()
  Sum.append(sum)
Ans=10**18
for k in range(1,n):
  p=0
  for i in range(n+k-1//k):
    if i==0:
      if n>=k:
        p+= (Sum[k])*5
      else:
        p+=(Sum[n])*5
        break
    else:
      if n> (k*i +k):
        p+= (Sum[k*i +k]-Sum[k*(i-1) +k])*(2*i +3)
      else:
        p+= (Sum[n]-Sum[k*(i-1) +k])*(2*i +3)
        break
  ans=(n+k)*x + p
  Ans=min(Ans,ans)
print(Ans)

### FIXED CODE ###

n,x=map(int,input().split())
line=list(map(int,input().split()))
Sum=[0]
sum=0
for i in range(n):
  sum+=line.pop()
  Sum.append(sum)
Ans=10**18
for k in range(1,n):
  p=0
  for i in range(n+k-1//k):
    if i==0:
      if n>=k:
        p+= (Sum[k])*5
      else:
        p+=(Sum[n])*5
        break
    else:
      if n> (k*i +k):
        p+= (Sum[k*i +k]-Sum[k*(i-1) +k])*(2*i +3)
      else:
        p+= (Sum[n]-Sum[k*(i-1) +k])*(2*i +3)
        break
  ans=(n+k)*x + p
  Ans=min(Ans,ans)
print(Ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# abc 127 d
# input
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
for i in range(m):
    s, l = map(int, input().split())
    if l > a[0]:
        for j in range(s):
            if a[j] < l:
                a[j] = l
            else:
                break
    a = sorted(a)
# output
print(sum(a))


### FIXED CODE ###

# -*- coding: utf-8 -*-
# abc 127 d
from operator import itemgetter
# input
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
upd = []
for i in range(m):
    upd.append(list(map(int, input().split())))
upd.sort(key=itemgetter(1), reverse=True)
# print(upd)
# output
f = len(a)
p = 0
for t in upd:
    for i in range(p, p+t[0]):
        if p < f:
            if a[p] < t[1]:
                a[p] = t[1]
            else:
                break
        else:
            break
        p += 1
print(sum(a))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

MOD = 998244353
A,B,C,D= map(int,input().split())
#A,B,C,D = 1,1,100,100

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res[:] for k in [0]*i]
    return res

memo = dpinit((C+1,D+1))
memo[A][B] = 1
for Y in range(A,C+1):
    memo[Y][1] = 1
for X in range(B,D+1):
    memo[1][X] = 1

def cnt(C,D):
    if memo[C][D] != 0:
        return memo[C][D]
    res = 0
    if C > A:
        res += (D * cnt(C-1,D) % MOD)
    if D > B:
        res += (C * cnt(C,D-1) % MOD)
    if C > A and D > B:
        res -= (cnt(C-1,D-1)*(C-1)*(D-1) % MOD)
    res %= MOD
    memo[C][D] = res 
    return res

print(cnt(C,D))






### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

MOD = 998244353
A,B,C,D= map(int,input().split())
#A,B,C,D = 1,1,3000,3000

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res[:] for k in [0]*i]
    return res

memo = dpinit((C+1,D+1))

memo[A][B] = 1
for Y in range(A,C+1):
    memo[Y][B] = pow(B,Y-A,MOD)
for X in range(B,D+1):
    memo[A][X] = pow(A,X-B,MOD)

for y in range(A+1,C+1):
    for x in range(B+1,D+1):
        memo[y][x] = (x*memo[y-1][x] + y*memo[y][x-1] - (x-1)*(y-1)*memo[y-1][x-1]) % MOD

print(memo[C][D])