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

from bisect import insort_left

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

d = []

for i in range(m):
    b,c = map(int,input().split())
    
    for j in range(b):
        d.append(c)        

d.sort()
d.reverse()

#print(a)
#print(d)

sum = 0
ln = len(d)
for i in range(n):
    if i < ln:
        if a[i] < d[i]:
            sum += d[i]
        else:
            sum += a[i]
    else:
        sum += a[i]

print(sum)


### FIXED CODE ###

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

d = []

bc = []
for i in range(m):
    b,c = map(int,input().split())
    bc.append([b,c])

bc = sorted(bc,key=lambda x:x[1],reverse=True)

for elm in bc:
    for i in range(elm[0]):
        d.append(elm[1])
        if len(d) >= n:
            break
    if len(d) >= n:
        break

d.sort()
d.reverse()

#print(a)
#print(d)

sum = 0
ln = len(d)
for i in range(n):
    if i < ln:
        if a[i] < d[i]:
            sum += d[i]
        else:
            sum += a[i]
    else:
        sum += a[i]

print(sum)
### BUGGY CODE ###

def hoge():
  from itertools import permutations
  N, M, R = map(int, input().split())
  r = map(int, input().split())
  r = [x - 1 for x in r]
  inf = float('inf')
  d = [[inf] * N for i in range(N)]

  for i in range(N):
      d[i][i] = 0

  for i in range(M):
      a, b, c = map(int, input().split())
      d[a-1][b-1] = c
      d[b-1][a-1] = c


  for k in range(N):
      for i in range(N):
          for j in range(N):
              t = d[i][k] + d[k][j]
              d[i][j] = min(d[i][j], t)


  ans = inf
  for i in permutations(r):
      tmphoge = len(i) - 1
      temp = 0
      for j in range(tmphoge):
          temp += d[i[j]][i[j+1]]
          if temp > ans:
              break
      ans = min(ans, temp)

  print(ans)
hoge()


### FIXED CODE ###

from itertools import permutations

def input_list():
    return list(map(int, input().split()))

def main():
    n, m, r = input_list()
    rlist = input_list()
    rlist = [r-1 for r in rlist]
    d = [[float('inf')]*n for i in range(n)]
    for i in range(n):
        d[i][i] = 0
    
    for i in range(m):
        a, b, c = input_list()
        d[a-1][b-1] = c
        d[b-1][a-1] = c

    for k in range(n):
        for i in range(n):
            for j in range(n):
                distance = d[i][k]+d[k][j]
                if d[i][j] > distance:
                    d[i][j] = distance

    ans = float('inf')
    for p in permutations(rlist):
        distance = 0
        for i in range(r-1):
            distance += d[p[i]][p[i+1]]

        if ans > distance:
            ans = distance

    print(ans)

main()
### BUGGY CODE ###

import math

n = int(input())
s = list(input())
sL = [] # B:1(R), W:0(L)
for i, x in enumerate(s):
    if i%2 == 0:
        if x == "W":
            sL.append(1)
        else:
            sL.append(0)
    if i%2 == 1:
        if x == "B":
            sL.append(1)
        else:
            sL.append(0)

count = 0
ans = 1
for i, x in enumerate(sL):
    if x==0:
        count += 1
    else:
        ans *= count
        count -= 1
ans *= math.factorial(n)
if count != 0:
    print(0)
else:
    print(ans%(10**9+7))

### FIXED CODE ###

n = int(input())
s = input()
count = 0
ans = 1 
for i, x in enumerate(s):
    if (i%2 == 0 and x == "B") or (i%2 == 1 and x == "W"): # B:1(R), W:0(L)
        count += 1
    else:
        ans *= count
        count -= 1
        ans %= (10**9+7)
if count != 0:
    print(0)
else:
    for i in range(1, n+1):
        ans *= i
        ans %= (10**9+7)
    print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
modulo = 998244353

sol = 3 ** n % modulo
s = sum(a)

from collections import Counter
dp = [Counter([0])]
for i, ai in enumerate(a):
    dp.append(dp[i] + dp[i])
    for key, item in dp[-2].items():
        dp[-1][key + ai] += dp[-2][key]


for key, item in dp[-1].items():
    if key >= s / 2:
        sol -= 3 * item

sol %= modulo

if s % 2 == 0:
    dp = [Counter([0])]
    for i, ai in enumerate(a):
        dp.append(dp[i].copy())
        for key, item in dp[-2].items():
            dp[-1][key + ai] += dp[-2][key]

    sol += 3*dp[-1][s //2]
    sol %= modulo

print(sol)

### FIXED CODE ###

import numpy as np
from math import ceil

n = int(input())
a = [int(input()) for _ in range(n)]
modulo = 998244353

s = sum(a)

dp = np.zeros(s + 1, dtype=np.int)
dp[0] = 1
for ai in a:
    dp[ai:] = 2 * dp[ai:] + dp[:-ai]
    dp[:ai] = 2 * dp[:ai]
    dp %= modulo
sol = 3 ** n % modulo
sol -= 3 * dp[ceil(s / 2) :].sum()


if s % 2 == 0:
    dp = np.zeros(s + 1, dtype=np.int)
    dp[0] = 1
    for ai in a:
        dp[ai:] = dp[ai:] + dp[:-ai]
        dp %= modulo

    sol += 3 * dp[s // 2]

sol %= modulo

print(sol)
### BUGGY CODE ###

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

res = 0
if N < B:
    res = (A * N) // B
else:
    res = ((A * (B - 1)) // B) - (A * ((B - 1) // B))
    i = B
    while i < N + 1:
        a = ((A * i) // B) - (A * (i // B))
        if res <= a:
            res = a
        else:
            break
        i += B

print(res)

### FIXED CODE ###

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

res = 0
if N < B:
    res = (A * N) // B
else:
    left = B - 1
    right = 10 ** 15
    while right - left > 1:
        mid = (right + left) // 2
        a = ((A * mid) // B) - (A * (mid // B))
        if res > a:
            right = mid
        else:
            res = a
            left = mid

print(res)
### BUGGY CODE ###

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

def main():

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

    ans = 1

    for i in A:
        ans *= i
    
    if ans > 10 ** 18:
        ans = -1

    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

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

def main():

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

    ans = 1

    if 0 not in A:
        for i in A:
            ans *= i
            if ans > 10 ** 18:
                ans = -1
                break

    else:
        ans = 0

    print(ans)


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

#!/usr/bin/env python3
import sys
import numpy as np
# import numba
# from numba import njit, b1, i4, i8, f8

input = sys.stdin.readline
mod = 998244353


def I():
    return int(input())


def MI():
    return map(int, input().split())


# @njit((i8, i8[:]), cache=True)
def main(N, steps):
    dp = np.zeros(N, np.int64)
    dp[0] = 1
    for i in range(N):
        if steps.size == 0:
            break
        if steps[-1] >= N:
            steps = steps[:-1]
        dp[steps] += dp[i]
        dp[steps] %= mod
        steps += 1

    return dp[N - 1]


N, K = MI()

steps = []
for _ in range(K):
    l, r = MI()
    steps += list(range(l, r + 1))

steps.sort()
steps = np.array(steps, np.int64)

print(main(N, steps))


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

# import numba
# from numba import njit, b1, i4, i8, f8

input = sys.stdin.readline
mod = 998244353


def I():
    return int(input())


def MI():
    return map(int, input().split())


# @njit((i8, i8[:]), cache=True)
def main(N, steps):
    dp = np.zeros(N + 1, np.int64)
    dpsum = np.zeros(N + 1, np.int64)
    dp[1] = 1
    dpsum[1] = 1
    for i in range(2, N + 1):
        for l, r in steps:
            li = i - r
            ri = i - l
            if ri < 0:
                continue
            li = max(li, 1)
            dp[i] += dpsum[ri] - dpsum[li - 1]
            dp[i] %= mod
        dpsum[i] = dpsum[i - 1] + dp[i]
        dpsum[i] %= mod

    return dp[N]


N, K = MI()

steps = []
for _ in range(K):
    l, r = MI()
    steps.append((l, r))


print(main(N, steps))
### BUGGY CODE ###

l = []
r = []
n,q = input().split()
N = int(n)
Q = int(q)
S = input()
for i in range(Q):
    L,R = input().split()
    l.append(int(L)-1)
    r.append(int(R)-1)
flag = [0 for i in S]
for i in range(len(S)-1):
    if((S[i] == "A")&(S[i+1] == "C")):
        flag[i] = 1
for j in range(Q):
    count = 0
    for i in range(l[j],r[j]):
        count = count + flag[i]
    print(count)

### FIXED CODE ###

n,q = (int(x) for x in input().split())
s = input()
l = []
r = []
for i in range(q):
    temp1,temp2 = (int(x) for x in input().split())
    l.append(temp1-1)
    r.append(temp2-1)

bb = []
bb.append(0)
# print(l)
for i in range(1,n):
    if s[i-1] == 'A' and s[i] == 'C':
        bb.append(bb[i-1] + 1)
    else:
        bb.append(bb[i-1])

for i in range(q):
    print(bb[r[i]] - bb[l[i]])
### BUGGY CODE ###

import collections
n = int(input())
s = [input() for i in range(n)]
c = collections.Counter(s)
a = []
for i in range(len(c)):
    if c.most_common()[i][1]==c.most_common()[0][1]:
        a.append(c.most_common()[i][0])
a = sorted(a)
for i in a:
  print(i)

### FIXED CODE ###

import collections

N = int(input())
S = list(input() for i in range(N))
S.sort()

common = collections.Counter(S).most_common()
N_common = common[0][1]

candidates = [cand for cand in common if cand[1] == N_common]

for i in sorted(candidates):
    print(i[0])
### BUGGY CODE ###

import re
n,q=map(int,input().split())
s=input()

a=[0]*(n+1)
for i in range(0,n+1):
    # print(s[0:i])
    a[i]+=len(re.findall("AC",s[0:i]))

for i in range(q):
    l,r=[int(i) for i in input().split()]
    print(a[r]-a[l])

### FIXED CODE ###

import re
n,q=map(int,input().split())
s=input()

a=[0]*(n+1)
for i in range(1,n+1):
    # print(s[i-1:i+1])
    if s[i-1:i+1]=="AC":
        a[i]=a[i-1]+1
    else:
        a[i]=a[i-1]

for i in range(q):
    l,r=[int(i) for i in input().split()]
    print(a[r-1]-a[l-1])
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,q = inpl()
g = [[]for i in range(n)]
c = [0 for i in range(n)]
seen = set()
for i in range(n-1):
    a,b = inpl()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
for i in range(q):
    a,b = inpl()
    c[a-1] += b
def dfs(node):
    for v in g[node]:
        if v in seen:
            continue
        c[v] += c[node]
        seen.add(v)
        dfs(v) 

seen.add(0)
dfs(0)
print(*c)

### FIXED CODE ###

n,q = map(int,input().split())
ki = [0] * (n+1)
c = [0] * (n+1)
for i in range(n-1):
    a,b = map(int,input().split())
    ki[b] = a
for i in range(q):
    p,x = map(int,input().split())
    c[p] += x

for i in range(2,n+1):
    c[i] += c[ki[i]]
print(*c[1:])
### BUGGY CODE ###

X=int(input())
N=X//100
for a in range(N+1):
  for b in range(N+1):
    for c in range(N+1):
      for d in range(N+1):
        for e in range(N+1):
          for f in range(N+1):
            if 100*a+101*b+102*c+103*d+104*e+105*f==X:
              print('1')
              exit()
print('0')

### FIXED CODE ###

X=int(input())
N=X%100
if N%5==0:
  if N//5<=X//100:
    print('1')
  else:
    print('0')
else:
  if N//5+1<=X//100:
    print('1')
  else:
    print('0')
### BUGGY CODE ###

N, K = map(int, input().split())
P = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))
ans = -float('inf')
for i in range(1, N+1):
    v = i
    score = 0
    size = 0
    while True:
        size += 1
        score += C[v]
        if i == P[v]:
            break
        v = P[v]

    if score > 0:
        tmp = score*(K//size-1)
        num = K%size+size
    else:
        tmp = 0
        num = min(K, size)
    
    v = i
    for _ in range(num):
        tmp += C[v]
        v = P[v]
        ans = max(tmp, ans)

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
P = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))
ans = -float('inf')
for i in range(1, N+1):
    v = i
    score = 0
    size = 0
    while True:
        size += 1
        score += C[v]
        if i == P[v]:
            break
        v = P[v]

    if score > 0:
        tmp = score*(K//size-1)
        num = K%size+size
    else:
        tmp = 0
        num = min(K, size)
    
    v = i
    for _ in range(num):
        tmp += C[v]
        v = P[v]
        ans = max(tmp, ans)

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

from heapq import heapify, heappush, heappop
from sys import maxsize

def dijkstra(start, INF):
    que = list()
    distance = [INF for _ in range(V)] # distance from
    distance[start] = 0
    heappush(que, (0, start))
    
    while len(que) > 0:
        dist, v = heappop(que)
        dist = abs(dist)
        if distance[v] < dist: continue
        for to, cost in edge[v]:
            if distance[v] + cost < distance[to]:
                distance[to] = distance[v] + cost
                heappush(que, (-distance[to], to))
    for d in distance:
        print(d if d != INF else 'INF')

V, E, r = map(int, input().split())
INF = maxsize
edge = [[] for _ in range(V)]
for i in range(E):
    s, t, cost = map(int, input().split())
    edge[s].append((t, cost))
dijkstra(r, INF)

### FIXED CODE ###

import heapq
from typing import List, TypeVar, Generic
T = TypeVar('T', int, float)


class Edge(Generic[T]):
    def __init__(self, dst: int, weight: T) -> None:
        self.dst: int = dst
        self.weight: T = weight

    def __lt__(self, e: 'Edge') -> bool:
        return self.weight > e.weight


class Graph(Generic[T]):
    def __init__(self, V: int) -> None:
        self.V: int = V
        self.E: List[List[Edge[T]]] = [[] for _ in range(V)]

    def add_edge(self, src: int, dst: int, weight: T) -> None:
        self.E[src].append(Edge(dst, weight))


class Node(Generic[T]):
    def __init__(self, v: int, cost: T) -> None:
        self.v: int = v
        self.cost: T = cost

    def __lt__(self, n: 'Node') -> bool:
        return self.cost < n.cost


class ShortestPath(Generic[T]):
    def __init__(self, G: Graph[T], inf: T = 10**9) -> None:
        self.G: Graph[T] = G
        self.inf: T = inf
        self.dist: List[T] = [self.inf] * self.G.V  # distance from start
        self.prev: List[int] = [-1] * self.G.V  # prev vertex of shortest path

    def run(self, start: int, goal: int = -1) -> None:
        que: List[Node] = list()
        self.dist[start] = 0
        heapq.heappush(que, Node[T](start, 0))

        while que:
            node: Node[T] = heapq.heappop(que)
            if self.dist[node.v] < node.cost:
                continue
            if goal != -1 and node.v == goal:
                return
            for edge in self.G.E[node.v]:
                if self.dist[node.v] + edge.weight < self.dist[edge.dst]:
                    self.dist[edge.dst] = self.dist[node.v] + edge.weight
                    heapq.heappush(que, Node(edge.dst, self.dist[edge.dst]))
                    self.prev[edge.dst] = node.v

    def getPath(self, end: int) -> List[int]:
        path: List[int] = [end]
        while self.prev[end] != -1:
            end = self.prev[end]
        return path[::-1]

def main() -> None:
    V, E, start = map(int, input().split())
    graph = Graph[int](V)
    for _ in range(E):
        s, t, d = map(int, input().split())
        graph.add_edge(s, t, d)
    inf = int(1e10)
    sp = ShortestPath[int](graph, inf)
    sp.run(start)
    for i in range(V):
        print(sp.dist[i] if sp.dist[i] != inf else "INF")

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

K, S = map(int, input().split())

ans = 0

for x in range(K+1):
    if x > S:
        break
    for y in range(K+1):
        if x + y > S:
            break
        for z in range(K+1):
            if x + y + z > S:
                break
            elif x + y + z == S:
                ans += 1
print(ans)

### FIXED CODE ###

K, S = map(int, (input().split()))
cnt = 0
for x in range(K+1):
    for y in range(K+1):
        if 0 <= S-(x+y) <= K:
            cnt += 1
print(cnt)
### BUGGY CODE ###

H, W, M = map(int, input().split())
hallline = [0 for i in range(H)]
wallline = [0 for i in range(W)]
for j in range(W):
    wallline[j] = 0
b = [[False for j in range(W)] for i in range(H)]

for i in range(M):
    tmp = list(map(lambda x: int(x) - 1, input().split()))
    hallline[tmp[0]] += 1
    wallline[tmp[1]] += 1
    b[tmp[0]][tmp[1]] = True

t = max(hallline)
s = max(wallline)

a = [i for i in range(H) if hallline[i] == t]
c = [i for i in range(W) if wallline[i] == s]

for i in a:
    for j in c:
        if not b[i][j]:
            print(t + s)
            exit()
print(t + s - 1)


### FIXED CODE ###

H, W, M = map(int, input().split())
hallline = [0 for i in range(H)]
wallline = [0 for i in range(W)]
b = {}

for i in range(M):
    tmp = list(map(lambda x: int(x) - 1, input().split()))
    hallline[tmp[0]] += 1
    wallline[tmp[1]] += 1
    b[(tmp[0], tmp[1])] = True

t = max(hallline)
s = max(wallline)

a = [i for i in range(H) if hallline[i] == t]
c = [i for i in range(W) if wallline[i] == s]

tmp = False

for i in a:
    for j in c:
        if (i, j) not in b.keys():
            print(t + s)
            tmp = True
            break
    if tmp:
        break
if not tmp:
    print(t + s - 1)
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
ans = 0

for i in range(N):
    for j in range(N):
        for k in range(N):
            if i != j and i != k and j != k:
                if L[i] < (L[j] + L[k]):
                    if L[j] < (L[k] + L[i]):
                        if L[k] < (L[i] + L[j]):
                            ans += 1
                            #print(L[i],L[j],L[k])

print(ans//6)

### FIXED CODE ###

# ３重ループではTLE
# a < b < c & c < a + b

import bisect
N = int(input())
L = sorted(list(map(int,input().split())))
ans = 0

for i in range(N):
    for j in range(i+1,N):
        t = L[i] + L[j]
        idx = bisect.bisect_left(L,t)
        ans += max(0, idx-j-1) # c < a + b の範囲を総取り
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
es = [[] for i in range(N)]
for i in range(M):
    l,r,d = map(int,input().split())
    l,r = l-1,r-1
    es[l].append((r,d))
    es[r].append((l,-d))

checked = [0] * N
for i in range(N):
    if checked[i]: continue
    dist = [-1] * N
    dist[i] = 0
    stack = [i]
    while stack:
        v = stack.pop()
        checked[v] = 1
        for to,d in es[v]:
            if dist[to] < 0:
                dist[to] = dist[v] + d
                stack.append(to)
            else:
                if dist[to] != dist[v] + d:
                    print('No')
                    exit()
print('Yes')


### FIXED CODE ###

N,M = map(int,input().split())
es = [[] for i in range(N)]

for i in range(M):
    l,r,d = map(int,input().split())
    l,r = l-1, r-1
    es[l].append((r,d))
    es[r].append((l,-d))

dist = [None] * N
for i in range(N):
    if dist[i] is not None: continue
    stack = [i]
    dist[i] = 0
    while stack:
        v = stack.pop()
        for to,d in es[v]:
            if dist[to] is None:
                stack.append(to)
                dist[to] = dist[v] + d
            elif dist[to] != dist[v] + d:
                print('No')
                exit()
print('Yes')
### BUGGY CODE ###

N, K, Q = map(int, input().split())
p = [K]*N
for _ in range(Q):
    p = list(map(lambda x : x-1, p))
    A = int(input())
    p[A-1] += 1
    
for ans in p:
    if ans <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

N, K, Q = map(int, input().split())
p = [0]*N
for _ in range(Q):
    #p = list(map(lambda x : x-1, p))
    A = int(input())
    p[A-1] += 1

for ans in p:
    if ans <= Q-K:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
ans=1
for i in range(n-1):
    tmp=a.count(a[i])+a.count(a[i]+1)+a.count(a[i]+2)
    ans=max(tmp,ans)
print(ans)

### FIXED CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
ans=1
cnt=[0]*(10**5+2)#a[i]+2
for i in range(n):
    cnt[a[i]]+=1
for i in range(n):
    tmp=cnt[a[i]]+cnt[a[i]+1]+cnt[a[i]+2]
    ans=max(tmp,ans)
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
items = list(map(int, input().split()))
items.sort(reverse=True)
for _ in range(M):
	items[0] //= 2
	items.sort(reverse=True)
print(sum(items))


### FIXED CODE ###

import heapq
N, M = map(int, input().split())
items = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(items)
for _ in range(M):
	tmp = heapq.heappop(items)
	heapq.heappush(items, int(tmp/2))
print(-sum(items))
### BUGGY CODE ###

import sys
from collections import deque
A, B = map(int, sys.stdin.readline().split())

a, b = deque([]), deque([])
for i in range(A, 0, -1):
    if A%i ==0:
        a.append(i)
    
for i in range(B, 0, -1):
    if B%i ==0:
        b.append(i)

a,b = set(a), set(b)
L = a&b
#print(L)
cnt =0
for l in L:
    tmp = 0
    for i in range(l-1, 1, -1):
        if l%i==0:
            tmp +=1
            break
    if tmp ==0:
        cnt+=1
print(cnt)

### FIXED CODE ###

import sys
import math

A, B = map(int, sys.stdin.readline().split())
C, D = max(A, B), min(A, B)

#ユーグリッド互除法
while True:
    amari = C%D
    C, D = D, amari
    if amari ==0:
        gcd = C
        break
#print(gcd)

#素因数分解
L = [1]
n = int(math.sqrt(gcd))
for i in range(2, n+1):
    while True:
        if gcd%i ==0:
            L.append(i)
            gcd = gcd//i
        else:
            break
if gcd>1:
    L.append(gcd)
L = set(L)
print(len(L))
### BUGGY CODE ###

import numpy as np

N,K=map(int, input().split())
P=list(map(int, input().split()))
Q=[sum(P[i:i+K]) for i in range(N-K+1)]

print((max(Q)+K)/2)

### FIXED CODE ###

import sys

N,K=map(int,input().split())
P=list(map(int,input().split()))
Q=[(1+p)/2 for p in P]
temp=sum(Q[:K])
ans=temp
for i in range(N):
  try:
    temp=temp-Q[i]+Q[i+K]
    ans=max(ans,temp)
  except:
    pass
else:
  print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np


def is_prime(a):
    flg = 1

    for i in range(2, a // 2 + 1):
        if is_prime(i) == 1:
            if a % i == 0:
                flg = -1
                break

    return flg


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

if a > b:
    max_num = a // 2
else:
    max_num = b // 2

ans = 1

for i in range(2, max_num // 2):
    if a % i == 0 and b % i == 0:
        if is_prime(i) == 1:
            ans += 1

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

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

soin_a = np.array([], dtype='int')
for i in range(2, int(np.sqrt(a)) + 1):
    if a % i == 0:
        soin_a = np.append(soin_a, i)
        while a % i == 0:
            a //= i
if a != 1:
    soin_a = np.append(soin_a, a)

soin_b = np.array([], dtype='int')
for i in range(2, int(np.sqrt(b)) + 1):
    if b % i == 0:
        soin_b = np.append(soin_b, i)
        while b % i == 0:
            b //= i
if b != 1:
    soin_b = np.append(soin_b, b)

ans = 1
for j in soin_a:
    if soin_b[soin_b == j].size != 0:
        ans += 1

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

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

li = [0]*(n+2)
lis = []
lis2 =[0]*(3*n)
lis2[1]=1

for i in range(k):
    l,r = map(int, input().split())
    li[l]+=1
    li[r+1]-=1

for i in range(1,n+1):
    li[i]+=li[i-1]
    if li[i]==1:
        lis.append(i)

for i in range(1,n+1):
    for j in lis:
        lis2[i]%=998244353
        lis2[i+j]+=lis2[i]

print(lis2[n])


### FIXED CODE ###

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

li = [0]*(n+2)
lis = []
lr=[]
lis2 =[0]*(3*n)
lis2[1]=1
lis2[2]=-1

for i in range(k):
    l,r = map(int, input().split())
    lr.append((l,r))

for i in range(1,n+1):
    lis2[i]+=lis2[i-1]
    lis2[i]%=998244353

    for j,k in lr:
        lis2[i+j]+=lis2[i]
        lis2[i+k+1]-=lis2[i]

print(lis2[n]%998244353)