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

import sys
sys.setrecursionlimit(1000000)
from collections import deque

INF = -1

nVertices, nEdges = map(int, input().split())
edges = [[] for _ in range(nVertices + 1)]
for _ in range(nEdges):
    u, v = map(int, input().split())
    edges[u].append(v)
s, t = map(int, input().split())

def getNextMoves(from_, v, depth):
    if depth == 3:
        if dist[v] == INF:
            dist[v] = dist[from_] + 1
            q.append(v)
        return
    for child in edges[v]:
        getNextMoves(from_, child, depth + 1)

dist = [INF] * (nVertices + 1)
dist[s] = 0
q = deque()
q.append(s)
while q:
    cur = q.popleft()
    getNextMoves(cur, cur, 0)
print(dist[t])

### FIXED CODE ###

from collections import deque

INF = -1

nVertices, nEdges = map(int, input().split())
edges = [[] for _ in range(nVertices + 1)]
for _ in range(nEdges):
    u, v = map(int, input().split())
    edges[u].append(v)
s, t = map(int, input().split())

dist = [[INF for _ in range(3)] for _ in range(nVertices + 1)]
dist[s][0] = 0
q = deque()
q.append((s, 0))
while q:
    curVertex, curDist = q.popleft()
    for nextVertex in edges[curVertex]:
        nextDist = curDist + 1
        if dist[nextVertex][nextDist % 3] == INF:
            dist[nextVertex][nextDist % 3] = nextDist
            q.append((nextVertex, nextDist))

print(dist[t][0] // 3 if dist[t][0] != INF else INF)
### BUGGY CODE ###

import math

n, m = map(int, input().split(" "))
aL = sorted(list(map(int, input().split(" "))), reverse=True)

for i in range(m):
    aL[0] //= 2
    for i in range(1, n):
        if aL[0] > aL[i]:
            aL = aL[1:i] + [aL[0]] + aL[i:]
            break

print(sum(aL))


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
aL = list(map(lambda x: int(x) * (-1), input().split(" ")))

heapq.heapify(aL)

for i in range(m):
    a = heapq.heappop(aL)
    a = int(a / 2)
    heapq.heappush(aL, a)

print(int(sum(aL) * -1))
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
count = 0
for i in range(q):
  l,r = input().split()
  l = int(l)
  r = int(r)
  t = s[l-1:r]
  count = 0
  for j in range(len(t)-1):
    if t[j:j+2] == "AC":
      count += 1
  print(count)
  count = 0

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
s_count = [0]
for i in range(len(s)):
  if s[i:i+2] == "AC":
    s_count.append(s_count[i] + 1)
  else:
    s_count.append(s_count[i])

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

n=int(input())
a=list(map(int,input().split()))
b=[]
c=[]
ans=0
for i in range(n):
  b.append(i+1-a[i])
  c.append(a[i]+i+1)
for i in range(n-1):
  for j in range(i+1,n):
    if b[j]==c[i]:
      ans+=1
print(ans)    

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]
c=[]
ans=0
for i in range(n):
  b.append(i+1-a[i])
  c.append(a[i]+i+1)
x=max(b)
if x<=0:
  print(0)
  exit()
else:
  ans=0
  b_=[0]*(x+1)
  for i in range(n):
    if 0<=b[i]<=x:
      b_[b[i]]+=1
  for i in range(n):
    if 0<=c[i]<=x:
      ans+=b_[c[i]]
  print(ans)
### BUGGY CODE ###

N = int(input())
D = [list(map(int, input().split())) for _ in range(N)]
D.sort(reverse=True)

A=0
B=0
for i in range(N):
  if i%2==0:
    A+=D[0][0]
    D.pop(0)
  else:
    tmp=max(D, key=lambda x:x[1])
    B+=tmp[1]
    D.remove(tmp)
  
print(A-B)

### FIXED CODE ###

N = int(input())
D=[]
b=0
for _ in range(N):
  A,B=map(int, input().split())
  D.append([A,B,A+B])
  b+=B
D.sort(reverse=True, key=lambda x:x[2])

ans=0
while D!=[]:
  ans+=D[0][2]
  D.pop(0)
  if D!=[]:
    D.pop(0)
  
print(ans-b)
### BUGGY CODE ###

n,*a=map(int,open(0).read().split())
dp=[[0]*(n+1)for _ in range(n+1)]
for t,(c,k) in enumerate(sorted((c,k) for k,c in enumerate(a))[::-1]):
	for i in range(t+1):
		j=t-i
		if dp[i+1][j]<=(s:=dp[i][j]+c*abs(i-k)):dp[i+1][j]=s
		if dp[i][j+1]<=(s:=dp[i][j]+c*abs(n-1-k-j)):dp[i][j+1]=s
print(max(dp[i][~i]for i in range(n+1)))

### FIXED CODE ###

n,*a=map(int,open(0).read().split())
dp=[[0]*(n+1)for _ in range(n+1)]
for t,(c,k) in enumerate(sorted((c,k) for k,c in enumerate(a))[::-1]):
	for i in range(t+1):
		j=t-i
		if dp[i+1][j]<dp[i][j]+c*abs(i-k):dp[i+1][j]=dp[i][j]+c*abs(i-k)
		if dp[i][j+1]<dp[i][j]+c*abs(n-1-k-j):dp[i][j+1]=dp[i][j]+c*abs(n-1-k-j)
print(max(dp[i][~i]for i in range(n+1)))
### BUGGY CODE ###

import math
import numpy as np

def main():
    h,w,k = tuple([int(t)for t in input().split()])

    s = [[int(i) for i in list(input())] for _ in range(h)]
    
    s = np.array(s)

    candidates = []

    for i in range(1<<h):
        s_subs = divide(s,i)
        cutnum = 0
        pos = 0

        for j in range(w):

            subsum = [np.sum(s_[:,pos:j])>k for s_ in s_subs]
            if any(subsum):
                pos = j-1
                cutnum+=1
        
        if any([np.sum(s_[:,pos:])>k for s_ in s_subs]):
            cutnum+=1


        candidates.append((bin(i).count('1')+cutnum))

    print(min(candidates))

def divide(s,i):
    subs = []
    counter = 0
    pos = 0
    while i!= 0:
        counter +=1
        if i%2==1:
            subs.append(s[pos:counter])
            pos = counter
        i >>=1

    subs.append(s[pos:])
    return subs
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import math
import functools
from operator import add

def main():
    h,w,k = tuple([int(t)for t in input().split()])

    s = [[int(i) for i in list(input())] for _ in range(h)]
    
    cusum = [accumelist(s_) for s_ in s]

    candidates = []

    for i in range(1<<(h-1)):
        subcu = divide(cusum,i)
        subs = divide(s,i)

        subcusum = []

        rowsum = []

        for sub_ in subcu:
            subcusum.append(functools.reduce((lambda a,b:list(map(add,a,b))),sub_))

        for sub_ in subs:
            rowsum.append(functools.reduce((lambda a,b:list(map(add,a,b))),sub_))


        cutnum = 0

        temp = [0]*len(subcusum)

        for j in range(w):
            for l in range(len(subcusum)):
                if subcusum[l][j]-temp[l]>k:
                    if rowsum[l][j]>k:
                        cutnum+=10000
                    temp = [x[j-1] for x in subcusum]
                    cutnum+=1
                    break
        
        candidates.append(cutnum+bin(i).count('1'))

    print(min(candidates))
            
def divide(s,i):
    subs = []
    counter = 0
    pos = 0
    while i!= 0:
        counter +=1
        if i%2==1:
            subs.append(s[pos:counter])
            pos = counter
        i >>=1
 
    subs.append(s[pos:])
    return subs

def accumelist(s):
    if s == []:
        return []
    res = [s[0]]
    for i in range(1,len(s)):
        res.append(res[i-1]+s[i])

    return res

def _add_(a,b):
    return map(add,a,b)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

HWD = input().split()
H = int(HWD[0])
W = int(HWD[1])
D = int(HWD[2])

num_array = [[0 for i in range(W)] for j in range(H)]
for i in range(H):
	row = input().split()
	for j in range(W):
		num_array[i][j] = int(row[j])

q = int(input())
count_list = [0 for i in range(q)]

for k in range(q):
	LR = input().split()
	L = int(LR[0])
	R = int(LR[1])

	num_where = []
	for i in range(int((R - L)/D) + 1):
		current_num = L + D*i
		for i in range(H):
			for j in range(W):
				if num_array[i][j] == current_num:
					num_where.append([i, j])
					break
			else:
				continue
			break

	count = 0
	for i in range(int((R - L)/D)):
		count +=  abs(num_where[i][0] - num_where[i+1][0]) + abs(num_where[i][1] - num_where[i+1][1])
	count_list[k] = count

for i in range(q):
	print(count_list[i])


### FIXED CODE ###

H,W,D = list(map(int, input().split()))
X = [[0,0] for i in range(H*W+1)]

for i in range(1, H+1):
	A = list(map(int, input().split()))
	for idx, a in enumerate(A):
		X[a] = [i, idx+1]

Q = int(input())
L = []
R = []
S = [0]*(H*W+1)

for i in range(Q):
	l,r = list(map(int, input().split()))
	L.append(l)
	R.append(r)

for i in range(D+1, H*W+1):
	S[i] = S[i-D] + abs(X[i][0]-X[i-D][0])+abs(X[i][1]-X[i-D][1])

for i in range(Q):
	print(S[R[i]] - S[L[i]])
### BUGGY CODE ###

N = int(input())

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

cnt = 0

for i in range(N):
    if i == 0:
        cnt += 1
    else:
        if all(list(map(lambda x:x > P[i], P[:i]))):
            cnt += 1

print(cnt)

### FIXED CODE ###

N = int(input())

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

m = 2 * (10 ** 5) + 1

cnt = 0

for i in range(N):
    if P[i] < m:
        cnt += 1
        m = min(P[i], m)
    
print(cnt)
### BUGGY CODE ###

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

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1
    if day > 250000:
        print(N*(N-1)//2)
        exit()
print(day)


### FIXED CODE ###

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

import sys
import time
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

start = time.time()

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1

    elapsed_time = time.time() - start
    if elapsed_time > 1:
        print(N*(N-1)//2)
        exit()
print(day)
### BUGGY CODE ###

h,w,k=map(int,input().split())
R=[]
A=[[0]*w for i in range(h)]
dp=[[[0]*4 for j in range(w)] for i in range(h)]

for i in range(k):
    x,y,v=map(int,input().split())
    x-=1;y-=1
    A[x][y]=v
    dp[x][y][1]=v
    dp[x][y][2]=v
    dp[x][y][3]=v;

for i in range(h):
    for j in range(w):
        for k in [0,1,2,3]:
            here=dp[i][j][k]
            if i<h-1:
                dp[i+1][j][0] = max(here,dp[i+1][j][0])
                dp[i+1][j][1] = max(here+A[i+1][j], dp[i+1][j][1])
            if j<w-1:
                dp[i][j+1][k] = max(dp[i][j+1][k], here)
                if k<=2:
                    dp[i][j+1][k+1]= max(dp[i][j+1][k+1],here+ A[i][j+1])


print( max(dp[-1][-1]))            


### FIXED CODE ###

import sys

R, C, K = map(int, input().split())
item = [[0] * (C + 1) for _ in range(R + 1)]  # dp配列と合わせるために, 0行目, 0列目を追加している.
for s in sys.stdin.readlines():
    r, c, v = map(int, s.split())
    item[r][c] = v

dp = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]
for i in range(R + 1):
    for j in range(C + 1):
        for k in range(4):
            here = dp[k][i][j]
            # 次の行に移動する場合
            if i + 1 <= R:
                # 移動先のアイテムを取らない場合
                dp[0][i + 1][j] = max(dp[0][i + 1][j], here)
                # 移動先のアイテムを取る場合
                dp[1][i + 1][j] = max(dp[1][i + 1][j], here + item[i + 1][j])
            # 次の列に移動する場合
            if j + 1 <= C:
                # 移動先のアイテムを取らない場合
                dp[k][i][j + 1] = max(dp[k][i][j + 1], here)
                # 現在のkが3未満のときのみ, 移動先のアイテムを取ることが可能
                if k < 3:
                    dp[k + 1][i][j + 1] = max(dp[k + 1][i][j + 1], here + item[i][j + 1])
ans = 0
for k in range(4):
    ans = max(ans, dp[k][-1][-1])
print(ans)
### BUGGY CODE ###

from collections import defaultdict
S = input()
T = input()
D = defaultdict(list)
L = [0] * 26
for i, s in enumerate(S):
  D[s].append(i + 1)
for i in range(26):
  c = chr(97 + i)
  L[i] = len(D[c])
def bsearch(t, pos, loop):
  d = D[t]
  l = L[ord(t) - 97]
  if l < 1:
    return -1, 0
  if pos < d[0]:
    return d[0], loop
  if d[l - 1] <= pos:
    loop += 1
    return d[0], loop
  low = 0
  high = l
  while high - low > 1:
    mid = (high - low) // 2
    if pos < d[mid]:
      high = mid
    else:
      low = mid
  return d[high], loop
pos = 0
loop = 0
for t in T:
  pos, loop = bsearch(t, pos, loop)
  if pos == -1:
    print(-1)
    break
else:
  print(len(S) * loop + pos)

### FIXED CODE ###

import bisect
S = input()
T = input()
D = [[] for _ in range(26)]
for i in range(26):
  D[i] = [0] * S.count(chr(97 + i))
P = [0] * 26
for i, s in enumerate(S):
  n = ord(s) - 97
  D[n][P[n]] = i + 1
  P[n] += 1
pos = 0
loop = 0
for t in T:
  n = ord(t) - 97
  if D[n] == []:
    print(-1)
    break
  _d = bisect.bisect(D[n], pos)
  _pos = D[n][_d % len(D[n])]
  if _pos <= pos:
    loop += 1
  pos = _pos
else:
  print(len(S) * loop + pos)
### BUGGY CODE ###

N = int(input())
A = list(int(x) for x in input().split())
a = len(A)
su = 0
for i in range(a):
    for j in range(i+1,a):
        su += A[i]*A[j]

print(su%(10**9+7))


### FIXED CODE ###

N = int(input())
A = list(int(x) for x in input().split())
B = [0]
a = len(A)
sa = sorted(A)
su = 0
p = 10**9+7

for i in range(a):
    B.append(B[i] + sa[i])

for j in range(a):
    su += sa[j]*B[j]

print(su%p)
### BUGGY CODE ###

import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
sys.setrecursionlimit(10**7)

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())

def main():
    N = I()
    P = LI()
    bar_ans = 0
    for i in range(N):
        for j in range(0,i+1):
            if P[j]<P[i]:
                bar_ans += 1
                break
            else:
                pass
    print(N - bar_ans)

main()



### FIXED CODE ###

import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
sys.setrecursionlimit(10**7)

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())

def main():
    N = I()
    P = LI()
    ans = 0
    min_num = P[0]
    for i in range(N):
        if min_num>=P[i]:
            ans += 1
            min_num = P[i]

    print(ans)

main()
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
count = 0
L.sort()
for i in range (N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            if L[k] < L[i] + L[j]:
                if L[j] < L[i] + L[k]:
                    count += 1
            else:
                break
    continue


print(count)


### FIXED CODE ###

from bisect import bisect_right
N = int(input())
L = list(map(int, input().split()))
count = 0
L.sort()
for i in range(N):
    for j in range(i):
        m = L[i] - L[j]
        k = bisect_right(L, m)
        n = max(0, j - k)
        count += n
print(count)
### BUGGY CODE ###

import collections

n = int(input())
List = [input() for i in range(n)]
res = []

c = collections.Counter(List)


leng = len(c)

res.append(c.most_common()[0][0])
for i in range(1, leng):
    if c.most_common()[i][1] >= c.most_common()[i-1][1]:
        res.append(c.most_common()[i][0])
    else:
        break

#res = sorted(res)
res.sort()
for j in range(len(res)):
    print(res[j])

### FIXED CODE ###

import collections

n = int(input())
List = [input() for i in range(n)]
res = []

c = collections.Counter(List)
m = 0
for v in c.values():
  m = max(m, v)
  
for k, v in c.items():
  if v == m:
    res.append(k)
    
res.sort()
for i in range(len(res)):
  print(res[i])
### BUGGY CODE ###

import bisect

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

ans=[]
def targetAdd(a):
    bisect.insort_left(ans, a)

for i in range(n):
    a, b = map(int, input().split())
    for j in range(b):
        targetAdd(a)

print(sum(ans[:m]))


### FIXED CODE ###

import bisect

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

ab=[]
for i in range(n):
    ab.append(list(map(int, input().split())))

ab = sorted(ab, key=lambda x: x[0])

def func():
    c=0
    ans=0

    for target in ab:
        for i in range(target[1]):
            ans+=target[0]
            c+=1

            if c == m:
                return ans
            

print(func())
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)

import copy

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

if((0 in x) == True):
    flag = n*[1]
    flag[x.index(0)] = 0
    state = x.index(0)
    count = 1
else:
    x.append(0)
    x = sorted(x)
    flag = (n+1)*[1]
    flag[x.index(0)] = 0
    state = x.index(0)
    count = 0

def search(x, flag, state, count, time, ans):
    if(count == k):
        if(ans > time): ans = time
        return ans

    if(sum(flag[:state]) != 0):
        tmp_state = state
        tmp_time = time
        while(True):
            state -= 1
            if(flag[state] == 1): break
        flag[state] = 0
        count += 1
        time += x[tmp_state] - x[state]

        ans = search(x, flag, state, count, time, ans)
        
        time = tmp_time
        count -= 1
        flag[state] = 1
        state = tmp_state

    if(sum(flag[state:]) != 0):
        tmp_state = state
        tmp_time = time
        while(True):
            state += 1
            if(flag[state] == 1): break
        flag[state] = 0
        count += 1
        time += x[state] - x[tmp_state]

        ans = search(x, flag, state, count, time, ans)
        
        time = tmp_time
        count -= 1
        flag[state] = 1
        state = tmp_state

    return ans

ans = search(x, flag, state, count, 0, int(1e9))

print(ans)

### FIXED CODE ###

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

if((0 in x) == True):
    state = x.index(0)
    k -= 1
else:
    x.append(0)
    x = sorted(x)
    state = x.index(0)

ans = int(1e10)
for left in range(k+1):
    right = k - left
    if(((state - left) >= 0) and ((state + right) <= (len(x) - 1))):
        if(right > 0): tmp = -2 * x[state-left]
        else: tmp = -1 * x[state-left]
        tmp += x[state+right]
        if(ans > tmp): ans = tmp

        tmp = -1 * x[state-left]
        if(left > 0): tmp += 2 * x[state+right]
        else: tmp += x[state+right]
        if(ans > tmp): ans = tmp

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

n,k = map(int,input().split())
h = sorted(list(map(int,input().split())), reverse=True)
for i in range(k):
  try:
    h.pop(0)
  except IndexError:
    break
print(sum(h))

### FIXED CODE ###

n,k = map(int,input().split())
h = sorted(list(map(int,input().split())), reverse=True)
if k >= n:
  print(0)
else:
  del h[:k]
  print(sum(h))
### BUGGY CODE ###

def gcd(x1,x2):
    r=0
    while True:
        if x1==x2:
            r=x1
            break
        elif x1<x2:
            x2=x2-x1
        else:
            x1=x1-x2
    return r

x = int(input())

ans=0

for a in range(1,x+1):
    for b in range(1,a+1):
        for c in range(1,b+1):
            gcd1=gcd(a,b)
            gcd2=gcd(gcd1,c)
            if a==b and b==c:
                ans += gcd2
            elif a==b or b==c or c==a:
                ans += 3*gcd2
            else:
                ans += 6*gcd2

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

def gcd(p,q): #p<q
    if q%p==0:
        return p
    return gcd(q%p,p)

x = int(input())

ans=0

for a in range(1,x+1):
    for b in range(1,a+1):
        for c in range(1,b+1):
            gcd1=gcd(a,b)
            gcd2=gcd(gcd1,c)
            if a==b and b==c:
                ans += gcd2
            elif a==b or b==c or c==a:
                ans += 3*gcd2
            else:
                ans += 6*gcd2

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
saisyo = min(A)
for _ in range(M):
    b, c = map(int, input().split())
    if c > saisyo:
        A += [c] * b

A.sort(reverse = True)

ans = 0
for i in range(N):
    ans += A[i]

print (ans)

### FIXED CODE ###

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

cb = []
for i in A:
    cb += [[i,1]]
for _ in range(M):
    b, c = map(int, input().split())
    cb += [[c, b]]
cb.sort(reverse = True)
#print (cb)

ans = 0
i = 0
j = 0
while i <= N:
    a = min(N-i, cb[j][1])
    ans += cb[j][0] * a
    j += 1
    i += a
    #print (ans)
    if i == N:
        print (ans)
        i += 1
### BUGGY CODE ###

a,b,x = map(int,input().split())
ans = 0
for i in range(a,b + 1):
    if i % x == 0:
        ans += 1
print(ans)

### FIXED CODE ###

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

if a != 0:
    print((b // x) - ((a - 1) // x))
else:
    print(b // x + 1)
### BUGGY CODE ###

from math import factorial as fac
def cc(n,r):
  return fac(n)//fac(r)//fac(n-r)
n, a, b, k = map(int, input().split())
mod = 998244353
ans = 0
for i in range(min(k//a+1,n+1)):
  jof = k-a*i
  if jof%b==0 and jof<=n*b:
    j = jof//b
    ans += cc(n,i)*cc(n,j)%mod
    ans %= mod
print(ans)

### FIXED CODE ###

n,a,b,k = map(int,input().split())
mod = 998244353
fun = [1]*(n+1)
for i in range(1,n+1):
  fun[i] = fun[i-1]*i%mod
rev = [1]*(n+1)
rev[n] = pow(fun[n],mod-2,mod)
for i in range(n-1,0,-1):
  rev[i] = rev[i+1]*(i+1)%mod
def nCr(n,r):
  if r > n:
    return 0
  return fun[n]*rev[r]%mod*rev[n-r]%mod
ans = 0
for i in range(min(n,k//a)+1):
  j = (k-a*i)//b
  if i*a+j*b == k and 0<=j<=n:
    ans += nCr(n,i)*nCr(n,j)
    ans %= mod
print(ans)
### BUGGY CODE ###

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

for i in range(n):
    b.append(a[i])
    b.reverse()

string = ""
for _ in b:
    string = string + str(_) + " "

print(string[:-1])

### FIXED CODE ###

import sys
from collections import deque

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

for i in range(n):
    if i % 2 != n % 2:
        b.appendleft(a[i])
    else:
        b.append(a[i])

for _ in b:
    sys.stdout.write(str(_) + " ")
sys.stdout.write("\n")
### BUGGY CODE ###

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

dp=[0]*(N+1)
dp[0]=1

for n in range(1,N+1):
	
  if n  in a:
    dp[n]=0
    
  else:
    dp[n]=(dp[n-1]+dp[n-2])%1000000007

print(dp[N])
    

### FIXED CODE ###

N,M,*a=map(int,open(0).read().split())

dp=[1]*(N+1)

for i in a:
  	dp[i]=0

for n in range(2,N+1):
    dp[n]=(dp[n-1]+dp[n-2])%1000000007*dp[n]

print(dp[N])