Harryxun/stf_run huggingface dataset:
N, M = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()                        # 破壊的。返り値はNone

# print(N, M)
# print(a)

num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]


dp = []
for i in range(N+1):
    n = [dp[i-num[a[j]]] for j in range(M) if i-num[a[j]] >= 0]
    if len(n) == 0:
        dp.append(0)
    else:
        dp.append(max(n) + 1)

# print(dp)

i = N
ans = ""
while True:
    # print("i", i)
    c = [(a[j], dp[i-num[a[j]]], dp[i]) for j in range(M)]
    # print("c", c)
    if dp[i] > 1:
        b = max([a[j] for j in range(M)
                 if i - num[a[j]] >= 0 and dp[i-num[a[j]]] + 1 == dp[i]])
        ans += str(b)
    else:
        b = max([a[j] for j in range(M)
                 if i - num[a[j]] == 0 and dp[i-num[a[j]]] + 1 == dp[i]])
        ans += str(b)
        break
    # print("ans", ans)
    i = i-num[b]
    # print(i)
    if i <= 0:
        break
print(ans)


### FIXED CODE ###

N, M = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()                        # 破壊的。返り値はNone

# print(N, M)
# print(a)

num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]


dp = [-999 for _ in range(N+1)]
dp[0] = 0
for i in range(N+1):
    n = [dp[i-num[a[j]]] for j in range(M) if i-num[a[j]] >= 0]
    if len(n) > 0:
        dp[i] = max(n) + 1

# print(dp)

i = N
ans = ""
for _ in range(dp[N]):
    # print("i", i)
    # c = [(a[j], dp[i-num[a[j]]], dp[i]) for j in range(M)]
    # print("c", c)
    if dp[i] > 1:
        b = max([a[j] for j in range(M)
                 if i - num[a[j]] >= 0 and dp[i-num[a[j]]] + 1 == dp[i]])
        ans += str(b)
    else:
        b = max([a[j] for j in range(M)
                 if i - num[a[j]] == 0 and dp[i-num[a[j]]] + 1 == dp[i]])
        ans += str(b)
        break
    # print("ans", ans)
    i = i-num[b]
    # print(i)
print(ans)
N,M = map(int,input().split())
pS = [[0,0] for i in range(M)]
for i in range(M):
  pS[i]= list(map(str,input().split()))
p = [0]*M
S = [0]*M
for i in range(M):
  p[i] = pS[i][0]
  S[i] = pS[i][1]
NM = N*M
AC = [0]*NM
WA = [0]*NM
i = 0
while i < M:
  if S[i] == 'WA':
    if AC[int(p[i])] != 1:
      WA[int(p[i])] = WA[int(p[i])]+1
    i = i+1
  elif S[i] == 'AC':
    AC[int(p[i])]=1
    i = i+1
  else:
    i = i+1
print(sum(AC),sum(WA))

### FIXED CODE ###

N,M = map(int,input().split())
p = ['0']*M
S = ['0']*M
for i in range(M):
  p[i],S[i]= map(str,input().split())
AC = [0]*(N+1)
WA = [0]*(N+1)
i = 0
for i in range(M):
  if S[i] == 'WA':
    if AC[int(p[i])] == 0:
      WA[int(p[i])] = WA[int(p[i])]+1
    else:
      None
  else:
    AC[int(p[i])]=1
count = 0
for i in range(N+1):
  if AC[i]==0:
    count = count+WA[i]
print(sum(AC),sum(WA)-count)
H,W = map(int, input().split())
S = [list(input()) for _ in range(H)] #データ形式はS[i][j]

eight = [[-1,-1],[0,-1],[1,-1], # 周囲8マスの定義
         [-1,0],[1,0],
         [-1,1],[0,1],[1,1]]

for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      for e in eight:
        target = S[i+e[0]][j+e[1]]
        if target and target != '#':
          if target == '.' :
            S[i+e[0]][j+e[1]] = 1
          else :
            S[i+e[0]][j+e[1]] += 1

for i in range(H):
  for j in range(W):
    print(S[i][j], end='')
  if i < H: print('')

### FIXED CODE ###

H,W = map(int, input().split())
S = [list(input()) for _ in range(H)] #データ形式はS[i][j]

eight = [[-1,-1],[0,-1],[1,-1], # 周囲8マスの定義
         [-1,0],[1,0],
         [-1,1],[0,1],[1,1]]

for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      for e in eight:
        if (0 <= i+e[0] < H) and (0 <= j+e[1] < W) :
          target = S[i+e[0]][j+e[1]]
          if target != '#' :
            if target == '.' :
              S[i+e[0]][j+e[1]] = 1
            else :
              S[i+e[0]][j+e[1]] += 1

for i in range(H):
  for j in range(W):
    print('0' if S[i][j] == '.' else str(S[i][j]), end='')
  if i < H: print('')
#A,B,K = [int(i) for i in input().rstrip().split()]
A,B,K = list(map(int, input().rstrip().split()))

#nums=[i for i in range(A,B+1)]
nums=list(range(A,B+1))

if K <= len(nums)//2:
  print(*(nums[:K] + nums[-K:]),sep="\n")
else:
  print(*nums,sep="\n")


### FIXED CODE ###

s = input().strip()

s_set=set(s)
print("Yes" if len(s_set)==3 else "No")
# https://atcoder.jp/contests/abc070/tasks/abc070_c

from functools import reduce
import math
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

# 最小公倍数を求める問題
# 参考：https://note.nkmk.me/python-gcd-lcm/
# 上記リンク先に最大公約数も載ってた

N = int(input())
T = []
for i in range(N):
    T.append(int(input()))

def lcm_base(x, y):
    x_y = x * y
    gcd_xy = math.gcd(x, y)
    ans = int(x_y / gcd_xy)
    return ans

def lcm_list(list):
    ans = reduce(lcm_base, list, 1)
    return ans

lcm = lcm_list(T)

print(lcm)


### FIXED CODE ###

N = int(input())
T = []
for i in range(N):
    T.append(int(input()))

def gcd(x, y):
    if x < y:
        x, y = y, x
    while x % y != 0:
        x, y = y, x % y
    return y


ans = T[0]
for i in range(1, N):
    ans *= T[i] // gcd(ans, T[i])

print(ans)
n=int(input())
s=str(input())
t=len(s)
#setの方が参照速度が速い
r=set()
g=set()
b=set()
a=0
for i in range(n):
    if s[i]=='R':
        r.add(i)
    if s[i]=='G':
        g.add(i)
    if s[i]=='B':
        b.add(i)
d=len(r)*len(g)*len(b)
for ri in r:
    for gi in g:
        if 2ri-gi in b:
            d-=1
        if 2gi-ri in b:
            d-=1
        if (gi+ri)/2 in b:
            d-=1

print(d)

### FIXED CODE ###

n=int(input())
s=str(input())
t=len(s)
r=set()
g=set()
b=set()
a=0
for i in range(n):
    if s[i]=='R':
        r.add(i)
    if s[i]=='G':
        g.add(i)
    if s[i]=='B':
        b.add(i)
d=len(r)*len(g)*len(b)
for ri in r:
    for gi in g:
        rg=gi-ri
        if rg+gi in b:
            d-=1
        if  ri-rg in b:
            d-=1
        if (gi+ri)/2 in b:
            d-=1

print(d)
S = input()
a = len(S)//2 + 1
A = S[:a-1]
reS=S[::-1]
B = reS[:a-1]
ans = 0
for i in range(a):
    if A[i] != B[i]:
        ans += 1
print(ans)        

### FIXED CODE ###

s = input()
r = s[::-1]
count = 0

for i in range(int(len(s))):
    if (s[i] != r[i]):
        count += 1

print(count//2)
N = int(input())
ans = "Yes"
arr = []
for i in range(N)
    arr.append(input())
    if not i == 1:
        if arr[i] in arr and arr[i-1][-1] == arr[i][0]
            pass
        else:
            ans = "No"
            break

print(ans)


### FIXED CODE ###

N = int(input())
ans = "Yes"
arr = []
for i in range(N):
    arr.append(input())
    if not i == 0:
        if arr[i-1][-1] == arr[i][0] and not arr[i] in arr[:-2]:
            pass
        else:
            ans = "No"
            break

print(ans)
n = int(input())
h = [int(input()) for i in range(n)]
result = 1

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

### FIXED CODE ###

n = int(input())
h = list(map(int,input().split(" ")))

result = 0
now_max = 0

for i in range(n):
    if h[i] >= now_max:
        result = result + 1
        now_max = h[i]

print(result)
m = int(input())
s = list(map(int, input()))
bs = [0] * m

cnt = 0
for i in range(m, 0, -1):
  b = sum(list(map(lambda x: bs[x-1], list(range(i, m+1, i)))))
  if s[i-1] is 0:
    if  b%2 is 0:
      bs[i-1] = 0
    else:
      cnt += 1
      bs[i-1] = 1
  else:
    if  b%2 is 0:
      cnt += 1
      bs[i-1] = 1
    else:
      bs[i-1] = 0

print(cnt)
print("".join(map(str, bs)))

### FIXED CODE ###

m = int(input())
s = list(map(int, input().split()))
bs = [0] * m

cnt = 0
for i in range(m, 0, -1):
  b = sum(list(map(lambda x: bs[x-1], list(range(i, m+1, i)))))
  if s[i-1] is 0:
    if  b%2 is 0:
      bs[i-1] = 0
    else:
      cnt += 1
      bs[i-1] = 1
  else:
    if  b%2 is 0:
      cnt += 1
      bs[i-1] = 1
    else:
      bs[i-1] = 0

print(cnt)
if cnt > 0:
  print(" ".join([str(i+1) for i, b in enumerate(bs) if b > 0]))
n = int(input())
h = list(map(int, input().split()))
H = [h]
ans = 0
while len(H) > 0:
  if [] in H:
    H.remove([])
    if len(H) == 0:
      break
  for i in range(len(H)):
    if len(H[i]) == 0:
      H.pop(i)
    elif 0 in H[i]:
      a = H[i][:H[i].index(0)]
      b = H[i][H[i].index(0) + 1:]
      H.append(a)
      H.append(b)
      H.pop(i)
      if [] in H:
        H.remove([])
        if len(H) == 0:
          break
    else:
      ans += min(H[i])
      H[i] = [H[i][j] - min(H[i]) for j in range(len(H[i]))]
      a = H[i][:H[i].index(0)]
      b = H[i][H[i].index(0) + 1:]
      H.append(a)
      H.append(b)
      H.pop(i)
      if [] in H:
        H.remove([])
        if len(H) == 0:
          break
print(ans)

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
H = [h]
ans = 0
while len(H) > 0:
  for e in H:
    if len(e) == 0:
      H.remove(e)
    elif 0 in e:
      a = e[:e.index(0)]
      b = e[e.index(0) + 1:]
      H.append(a)
      H.append(b)
      H.remove(e)
      if [] in H:
        H.remove([])
        if len(H) == 0:
          break
    else:
      ans += min(e)
      c = [e[j] - min(e) for j in range(len(e))]
      a = c[:c.index(0)]
      b = c[c.index(0) + 1:]
      H.append(a)
      H.append(b)
      H.remove(e)
      if [] in H:
        H.remove([])
        if len(H) == 0:
          break
    if [] in H:
      H.remove([])
      if len(H) == 0:
        break
print(ans)
# 方針　union findで解く
n, m = map(int, input().split())  # 入力の受け取り
par = [i for i in range(1, n + 1)]  # 親のリストを作成


# find関数を作成。自分の値とリスト番号を比べ、親ならば返し、子ならば親を探す
# par[x-1]としているのは、例えばpar[0]=1になっているため
def find(x):
    if par[x - 1] == x:
        return x
    else:
        par[x - 1] = find(par[x - 1])
        return par[x - 1]


# union関数を作成。2つの引数の親を比べ、違う場合は一方の親を一方の子にする
def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x - 1] = y


# 入力すべてでunionする
for j in range(m):
    a, b = map(int, input().split())
    union(a, b)

# n人の親を探して、リストsに入れ、それぞれ親の数をカウントし、最頻値をグループ数とする。
s = [find(i) for i in range(1, n + 1)]
import collections
c = collections.Counter(s)
print(max(c.values()))


### FIXED CODE ###

import collections
n, m = map(int, input().split())
par = list(range(2 * n))

# print(par)


# union find(parには0も入れているので、par[1]=1になる)
def find(x):

    while par[x] != x:
        tmp = par[x]
        par[x] = par[par[x]]
        x = par[x]

    return x


def union(x, y):
    x1 = find(x)
    y1 = find(y)
    if x1 != y1:
        par[x1] = y1


# 各要素をunionする
for j in range(m):
    a, b = map(int, input().split())
    union(a - 1, b - 1)

s = [0 for i in range(n + 5)]

# 1～nの親を探してsに入れていき、一番多い親を答えにする
for k in range(n):
    s[find(k)] += 1

print(max(s))
n, m = map(int, input().split())
l = [[] for _ in range(m)]
for i in range(m):
  a, b  = map(int, input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)

import itertools
ans = 0
for p in itertools.permutations(range(n)):
    if p[0] == 0:
        flag = 1
    else:
        flag = 0
        for i in range(n-1):
            if not p[i+1] in l[p[i]]:
                flag = 0
        if flag == 1:
            ans += 1
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
L = [[] for i in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
    
import itertools
count = 0
for p in itertools.permutations(range(N)):
    if p[0] == 0:
#         print("p",p)
        flag = True
        for i in range(N-1):
#             print(p[i+1], L[p[i]])
            if not p[i+1] in L[p[i]]:
                flag = False
#             print(flag)
        if flag:
            count += 1
print(count)
#!/usr/bin/env python3

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

candidates = [i for i in range(N)]

for k in range(M - 1):
    A = map(int, input().split())
    for Ai in A:
        try:
            index = candidates.index(Ai)
            del candidates[index]
        except ValueError:
            pass

print(len(candidates))


### FIXED CODE ###

#!/usr/bin/python3

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

A = []
for k in range(N):
    Ai = [i for i in map(int, input().split())]
    _M = Ai.pop(0)
    A.append(Ai)

res = A[0]
for k in range(N - 1):
    res = list(set(res) & set(A[k + 1]))


print(len(res))
def rot(v):
    v = [-v[1],v[0]]
    return v

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

u = [S[2]-S[0],S[3]-S[1]]
v = rot(u)
w = rot(v)

X3 = [S[2]+v[0],S[3]+v[1]]
X4 = [X3[0]+w[0],X3[1]+w[1]]

print(*X3, *X4)

### FIXED CODE ###

def rot(v):
    v = [-v[1],v[0]]
    return v

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

u = [S[2]-S[0],S[3]-S[1]]
v = rot(u)
w = rot(v)

X3 = [S[2]+v[0],S[3]+v[1]]
X4 = [X3[0]+w[0],X3[1]+w[1]]

print(*(X3+X4))
n,k=map(int,input().split())
r,s,p=map(int,input().split())
t=input()
point=0
l=[]
point_list=[r,s,p]
kind=['r','s','p','r']
for i in range(n):
  for j in range(len(kind)-1):
    if t[i]==kind[j]:
      if i-k>=0 and t[i]==kind[l[i-k]+1]:
        if i+k<n and t[i+k]==kind[j+1]:
          if j==2:j=-1
          l.append(j+1)
        else:
          l.append(j)
      else:
        point+=point_list[j-1]
        if j==0:j=3
        l.append(j-1)
      break
print(point)

### FIXED CODE ###

str1,str2=input().split()
print(str2+str1)
N , L= map(int,input().split())
lst = list()
Str = ''
for i in range(L):
    lst.append(input())
for k  in range(N):
    for j in range(N-1):
        if lst[j] >= lst[j+1]:
            lst[j],lst[j+1] = lst[j+1] ,lst[j]

for i in lst:
    Str += i
print(lst)


### FIXED CODE ###

N,L=map(int, input().split())
S=[]
for i in range(N):
    S.append(input())
S.sort()
result=''
for j in range(N):
    result+=S[j]     
print(result)
import sys

t = sys.stdin.readline()
a = sys.stdin.readline()
b = sys.stdin.readline()

t1 = t.rstrip()
a1 = a.rstrip()
b1 = b.rstrip()

T = int(t1)
A = int(a1)
B = int(b1)


p1 = A*T

if B < p1:
    print(B)
elif B > p1:
    print(p1)
else:
    print(B)


### FIXED CODE ###

import sys
t = sys.stdin.readline()

t1 = t.rstrip()

t2 = t1.split(' ')

T = int(t2[0])
A = int(t2[1])
B = int(t2[2])
p1 = A*T

if B < p1:
    print(B)
elif B > p1:
    print(p1)
else:
    print(B)
N, M, Q = map(int, raw_input().split())
for _ in range(M):
LR = [map(int, raw_input().split()) for _ in range(M)]
pq = [map(int, raw_input().split()) for _ in range(Q)]

table = [[0 for _i in range(N+1)] for _j in range(N+1)]
for line in LR:
    table[LR[0]][LR[1]] += 1
for question in pq:
    p = question[0]
    q = question[1]
    ans = 0
    for j in range(p, q+1):
        ans += table[p][j]
    print(ans)

### FIXED CODE ###

N, M, Q = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]
pq = [list(map(int, input().split())) for _ in range(Q)]

table = [[0 for _i in range(N+1)] for _j in range(N+1)]
accum = [[0 for _i in range(N+1)] for _j in range(N+1)]
accum2 = [[0 for _i in range(N+1)] for _j in range(N+1)]

for line in LR:
    table[line[0]][line[1]] += 1
# よこ
for i in range(1, N+1):
    for j in range(1, N+1):
        accum[i][j] = accum[i][j-1] + table[i][j]
# 縦
for i in range(1, N+1):
    for j in range(1, N+1):
        accum2[i][j] = accum2[i-1][j] + accum[i][j]

# for i in range(1, N+1):
#     for j in range(i, N+1):
#         ans[i][j] = sum([accum[k][j] - accum[k][i-1] for k in range(i, j+1)])

for question in pq:
    p = question[0]
    q = question[1]
    print(accum2[q][q] - accum2[p-1][q] - accum2[q][p-1] + accum2[p-1][p-1])
a,b = map(int,raw_input().split())

if a > b:
print "a > b"

elif a < b:
print "a < b"

else:
print "a == b"

### FIXED CODE ###

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

if a>b:
    print 'a > b'
    
elif a<b:
    print 'a < b'
    
else:
    print 'a == b'
def Sol(a,b,c,d):
    
    if a%d != 0:
        m_aoki = int(a/d) + 1
    else:
        m_aoki = int(a/d)

    if c%b != 0:
        m_taka = int(c/b) + 1
    else:
        m_taka = int(c/b)
        
    if m_taka >= m_aoki:
        print("YES")
    else:
        print("NO")

    return

    

#for t in range(int(input())):
n,k,c,d = map(int,input().split())
#n = int(input())
#arr = []
#for i in range(n):
#    arr.append(input())
#arr = list(map(int,input().split()))
#k = input()
#n = int(input())
Sol(n,k,c,d)


### FIXED CODE ###


def Sol(s,w):
    
    if s>w:
        print("safe")
    else:
        print("unsafe")
    
    return

    

#for t in range(int(input())):
n,k = map(int,input().split())
#n = int(input())
#arr = []
#for i in range(n):
#    time = list(map(int,input().split()))
#    time = time[0] + (time[1]/60)
#    arr.append(time)
#arr = list(map(int,input().split()))
#k = input()
#n = int(input())
Sol(n,k)
a,b = input().split()
if a==b:
  print(H)
else:
  print(D)

### FIXED CODE ###

a,b = input().split()
if a==b:
  print("H")
else:
  print("D")
# import math

S = input()
K = int(input())

ps = []

for s in S:
    i = int(s)
    if(i == 1):
        p = -1
    else:
        p = 5*(10**15) * math.log2(i)
    ps.append(p)

sum = 0
index = 0
    
if K == 1:
    print(S[0])
else:
    for p in ps:

        if not p == -1:
            sum += p
        else:
            K -= 1

        if math.log2(K) < sum:
            #print(index)
            print(S[index])
            break
        index += 1



### FIXED CODE ###

S = input()
K = int(input())

for i, k in enumerate(range(K)):
    if S[k] != '1':
        print(S[k])
        break
    if i == K - 1:
        print('1')
# coding: utf-8

dishes = [int(input()) for _ in range(5)]

min_index = min([(i, d % 10) for i, d in enumerate(dishes) if d % 10 != 0], key=lambda x: x[1])[0]
min_dish = dishes[min_index]
dishes.remove(min_dish)
cooking_time = [d + 10 - (10 if d % 10 == 0 else (d % 10)) for d in dishes]
print(sum(cooking_time) + min_dish)


### FIXED CODE ###

# coding: utf-8

dishes = [int(input()) for _ in range(5)]

min_loss = 10
min_dish = dishes[0]
cooking_time = []
for d in dishes:
    loss = 0 if d % 10 == 0 else d % 10
    if loss != 0 and min_loss > loss:
        min_loss = loss
        min_dish = d
dishes.remove(min_dish)
for d in dishes:
    loss = 0 if d % 10 == 0 else 10 - d % 10
    cooking_time.append(d + loss)
print(sum(cooking_time) + min_dish)
from collections import deque
import copy
s = input()
q_ = int(input())
query = [input().split() for _ in range(q_)]
l = deque([s])

for q in query:
    if q[0] == '1':
        l = copy.deepcopy([''.join(l)[::-1]])
    elif q[0] == '2':
        if q[1] == '1':
            l.appendleft(q[2])
        else:
            l.append(q[2])

print(''.join(l))

### FIXED CODE ###

from collections import deque
import copy
s = input()
q_ = int(input())
query = [input().split() for _ in range(q_)]
l = deque(s)
flag = 0

for q in query:
    if q[0] == '1':
        flag += 1
        continue
    elif q[0] == '2':
        if (int(q[1]) + flag) % 2 == 1:
            l.appendleft(q[2])
        else:
            l.append(q[2])

if flag % 2 == 1:
    l.reverse()

print(''.join(l))
n = int(input())
s = [2,3,4,5,6,7,8,9]
frag = True

if n<=9:
    print("Yes")
else:
    for i in s:
        if n % i == 0:
            flag = False
            print("Yes")
            break
if flag:
    print("No")

### FIXED CODE ###

n = int(input())
s = [2,3,4,5,6,7,8,9]
flag = True
 
if 1<= n <=9:
    print("Yes")
    flag = False
else:
    for i in s:
        if n % i == 0 and n/i <= 9:
            flag = False
            print("Yes")
            break
if flag:
    print("No")
import math

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

def comb(n, r):
    if n == 0:
        return 0
    if r == 0:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

if N + M < 2:
    print(0)
elif N == 1 and M == 1:
    print(0)
else:
    ans = comb(N, 2) + comb(M, 2)
    print(ans)

### FIXED CODE ###

import math
 
N, M = map(int, input().split())
 
def comb(n, r):
    if n == 0:
        return 0
    if r == 0:
        return 0
    if n < 2:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
 
if N + M < 2:
    print(0)
elif N == 1 and M == 1:
    print(0)
else:
    ans = comb(N, 2) + comb(M, 2)
    print(ans)
import sys
input = sys.stdin.readline
import numpy as np
def print_ans(A, B, C, D):
    """Test Case
    >>> print_ans(4, 9, 2, 3)
    2
    >>> print_ans(10, 40, 6, 8)
    23
    >>> print_ans(314159265358979323, 846264338327950288, 419716939, 937510582)
    532105071133627368
    """
    ar = np.arange(A, B + 1)
    cr = ar[ar % C != 0]
    dr = cr[cr % D != 0]
    print(len(dr))

if __name__ == '__main__':
    A, B, C, D = map(int, input().rstrip().split())
    print_ans(A, B, C, D)




### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x
def calc(x, C, D, l):
    x1 = x // C
    x2 = x // D
    x3 = x // l
    return x - x1 -x2 + x3

def print_ans(A, B, C, D):
    """Test Case
    >>> print_ans(4, 9, 2, 3)
    2
    >>> print_ans(10, 40, 6, 8)
    23
    >>> print_ans(314159265358979323, 846264338327950288, 419716939, 937510582)
    532105071133627368
    """
    # Greatest common divisor
    g = gcd(max(C,D),min(C,D))
    # Least common multiple
    l = C * D // g
    print(calc(B, C, D, l) - calc(A - 1, C, D, l))



if __name__ == '__main__':
    A, B, C, D = map(int, input().rstrip().split())
    print_ans(A, B, C, D)
n=int(input())
d=list(map(int,input().split()))

dd=sorted(d)

print(dd[n/2+1]-dd[n/2-1])

### FIXED CODE ###

n = int(input())
d = sorted(list(map(int,input().split())))

print(d[n//2]-d[n//2-1])
n = int(input())
enemy = list(map(int, input().split()))
beat = list(map(int, input().split()))

def hoge(index, index1):
  if(index == 0 and index1 == 0):
  	return min([enemy[0], beat[0]])
  elif(index1 - index == 1):
    return min([enemy[index1], beat[index] - hoge(index, index)])
  else:
    return min([enemy[index] - hoge(index - 1, index), beat[index] ])
  
res = 0
for i in range(n):
	print(i)  
	res += hoge(i, i) + hoge(i, i+1)
print(res)


### FIXED CODE ###

n = int(input())
enemy = list(map(int, input().split()))
beat = list(map(int, input().split()))
ans = 0 
for i in range(n):
  #左を全力で倒す
  left = min([enemy[i], beat[i]])
  ans += left
  enemy[i] -= left
  beat[i] -= left
  
  right = min([enemy[i+1], beat[i]])
  ans += right
  enemy[i + 1] -= right
  beat[i] -= right
  
print(ans)
import sys

x = []

max = -10**9

for line in sys.stdin.readline()
  x.append(line)

length = int(x[0])

x.remove(x[0])

for i in range(0, length):
  for j in range(i + 1, length):
    sa = int(x[j]) - int(x[i])
    if max < sa:
      max = sa

print max

### FIXED CODE ###

import sys

x = []

for line in sys.stdin.readlines():
  x.append(line.strip())

max = -(10**9)
min = int(x[1])

for i in range(2, int(x[0])+1):
  sa = int(x[i]) - min
  if max < sa:
    max = sa
  if min > int(x[i]):
    min = int(x[i])

  

print max
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)

nums = {}
nums[1] = 2
nums[2] = 5
nums[3] = 5
nums[4] = 4
nums[5] = 5
nums[6] = 6
nums[7] = 3
nums[8] = 7
nums[9] = 6

dp = [-float('inf')]*(N+1)
dp[0] = 0

for i in range(N+1):
    for a in A:
        if i-nums[a] >= 0:
            dp[i] = max(dp[i], dp[i-nums[a]]+1)

ans = ""
i = N
keta = dp[-1]
while i > 0 and keta > 0:
    keta -= 1
    for a in A:
        if dp[i]-1 == dp[i-nums[a]]:
            ans += str(a)
            i = i-nums[a]
            break
print(ans)


### FIXED CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)

nums = {}
nums[1] = 2
nums[2] = 5
nums[3] = 5
nums[4] = 4
nums[5] = 5
nums[6] = 6
nums[7] = 3
nums[8] = 7
nums[9] = 6

dp = [-float('inf')]*(N+1)
dp[0] = 0

for i in range(N+1):
    for a in A:
        if i-nums[a] >= 0:
            dp[i] = max(dp[i], dp[i-nums[a]]+1)

ans = ""
i = N
while i > 0:
    for a in A:
        if i >= nums[a] and dp[i]-1 == dp[i-nums[a]]:
            ans += str(a)
            i = i-nums[a]
            break
print(ans)