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

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

d = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
c = [(i, d[i]) for i in A]
minpos = min(c, key=lambda x:x[1])[1]

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

for i in range(minpos, N+1):
    for n, cost in c:
        if i-cost<0 or 0<i-cost<minpos: continue
        a = dp[i]
        b = dp[i-cost] + n * (10**(digit[i-cost]))
        if a<b:
            dp[i] = b
            digit[i] = digit[i-cost] + 1

print(dp[N])

### FIXED CODE ###

from collections import defaultdict as dd

n,m=map(int,input().split())
*a,=map(int,input().split())
dp=[-1]*(n+1)
ans = [0] * (n + 1)

cost={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}

d={i:cost[i] for i in a}

dp[0] = 0
for i in range(1,n+1):
    for j in range(10)[::-1]:
        if not j in d:
            continue
        if cost[j] > i:
            continue
        if dp[i] < dp[i - cost[j]] + 1:
            dp[i] = dp[i - cost[j]] + 1
            ans[i] = j

S = ""
pos = n

while pos != 0:
    S += str(ans[pos])
    pos -= cost[ans[pos]]

print(S)
### BUGGY CODE ###

n = int(input())
s = len(input())
mod = 10**9+7
dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
  dp[i][0] = (dp[i-1][0] + dp[i-1][1])%mod
  for j in range(1,min(n,i+1)):
    dp[i][j] = (dp[i-1][j-1]*2 + dp[i-1][j+1])%mod
  dp[i][n] = dp[i-1][n-1]*2%mod
s2 = pow(2,s,mod)
rev = pow(s2,mod-2,mod)
print(dp[n][s]*rev%mod)


### FIXED CODE ###

n = int(input())
s = len(input())
mod = 10**9+7
dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
  dp[i][0] = (dp[i-1][0] + dp[i-1][1])%mod
  for j in range(1,n):
    dp[i][j] = (dp[i-1][j-1]*2 + dp[i-1][j+1])%mod
  dp[i][n] = dp[i-1][n-1]*2%mod
s2 = pow(2,s,mod)
rev = pow(s2,mod-2,mod)
print(dp[n][s]*rev%mod)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [[int(i) for i in input().split()] for i in range(m)]
bc.sort(key = lambda x:x[1], reverse = True)


for b, c in bc:
        a.sort()
        if c < a[0]:
                break
        for i in range(b):
                if a[i] < c:
                        a[i] = c
                elif a[i] >= c:
                        break

print(sum(a)) 

### FIXED CODE ###

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

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

a.sort()

a_count = 0
for b, c in bc:
        if c > a[a_count]:
                for i in range(b):
                        if c > a[a_count]:
                                a[a_count] = c
                                a_count += 1    
                        else:
                                break
                        if a_count == n:
                                        break

        else:
                break
        if a_count == n:
                break        

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

from collections import deque

H,W = map(int,input().split())
A = [input() for i in range(H)]

L = [[float("inf") for x in range(W)] for y in range(H)]



dxy = [(-1,0), (1,0), (0,-1), (0,1)]

Q = deque()

for y in range(H) :
    for x in range(W) :
        if A[y][x] != "#" :
            continue
        
        L[y][x] = 0
        
        Q.append((y,x))

while Q :
    y,x = Q.popleft()

    for dy,dx in dxy :
        ny = y+dy
        nx = x+dx

        if (ny < 0) or (ny >= H) or (nx < 0) or (nx >= W) :
            continue

        if L[ny][nx] <= (L[y][x] + 1) :
            continue
        
        L[ny][nx] = L[y][x] + 1
        
        Q.append((ny,nx))

ans = 0

for y in range(H) :
    for x in range(W) :
        ans = max(ans, L[y][x])
print(ans)



### FIXED CODE ###

from collections import deque

H,W = map(int,input().split())
A = [input() for i in range(H)]

L = [[float("inf") for x in range(W)] for y in range(H)]



dxy = [(-1,0), (1,0), (0,-1), (0,1)]

Q = deque()

for y in range(H) :
    for x in range(W) :
        if A[y][x] != "#" :
            continue
        
        L[y][x] = 0
        
        Q.append((y,x))

while Q :
    y,x = Q.popleft()

    for dy,dx in dxy :
        ny = y+dy
        nx = x+dx

        if (ny < 0) or (ny >= H) or (nx < 0) or (nx >= W) :
            continue

        if L[ny][nx] <= (L[y][x] + 1) :
            continue
        
        L[ny][nx] = L[y][x] + 1
        
        Q.append((ny,nx))

ans = 0

for y in range(H) :
    ans = max(ans, max(L[y]))
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
n = 0

for q in range(Q):
  R = input()
  
  if int(R[0])==1:
    n = (n+1)%2
  else:
    T,F,C = R.split()
    F = int(F)
    
    if n==0 and F==1:
      S = C+S
    elif n==0 and F==2:
      S = S+C
    elif n==1 and F==1:
      S = S+C
    else:
      S = C+S

if n==0:
  print(S)
else:
  print(S[::-1])

### FIXED CODE ###

S = input()
Q = int(input())
T = ""

for q in range(Q):
  que = input().split()
  if que[0]=="1":
        S,T = T,S
  else:
    if que[1]=="1":
      T+=que[2]
    else:
      S+=que[2]

print(T[::-1]+S)
### BUGGY CODE ###

import time, random
now = time.time()

d = int(input())
clst = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(d)]
last = [0 for _ in range(26)]

def score_minus(d, q):
    minus = 0
    for i, (c, ls) in enumerate(zip(clst, last)):
        if i == q:
            continue
        minus += c * (d + 1 - ls)
    return minus

def check(t):
    def score_minus(d):
        minus = 0
        for c, ls in zip(clst, last):
            minus += c * (d - ls)
        return minus
        
    last = [0 for _ in range(26)]
    ans = 0
    for d, num in enumerate(t, start = 1):
        ans += s[d - 1][num - 1]
        last[num - 1] = d
        ans -= score_minus(d)
    return ans
    
t_lst = []
for i in range(d):
    tmp = -10 ** 10
    for q in range(26):
        tmp_score = s[i][q] - score_minus(i, q)
        if tmp_score > tmp:
            tmp = tmp_score
            max_q = q
    last[max_q] = i
    t_lst.append(max_q + 1)

ans = check(t_lst)

while time.time() - now < 1.9:
    d_change = random.randint(0, d - 1)
    q_change = random.randint(1, 26)
    old_d = t_lst[d_change]
    if old_d == q_change:
        continue
    t_lst[d_change]  = q_change
    ans_tmp = check(t_lst)
    if ans_tmp > ans:
        ans = ans_tmp
    else:
        t_lst[d_change] = old_d

for t in t_lst:
    print(t)


### FIXED CODE ###

d = int(input())
clst = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(d)]
last = [0 for _ in range(26)]

def score_minus(d, q):
    minus = 0
    for c, ls in zip(clst, last):
        minus += c * (d - ls)
    minus -= clst[q] * (d - last[q])
    return minus
    
ans = 0
for i in range(d):
    tmp = 0
    for q in range(26):
        tmp_score = s[i][q] - score_minus(i, q)
        if tmp_score > tmp:
            tmp = tmp_score
            max_q = q
    print(max_q + 1)
    last[max_q] = i
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)
for i in range(N):
    tmp = 0
    for j in range(i+1, N):
        if(i+1 == A[j]):
            tmp += 1
    print(tmp)

### FIXED CODE ###


N = int(input())
A = list(map(int, input().split()))
dp = [0]*N
for i in range(len(A)):
    dp[A[i]-1] += 1
for i in range(N):
    print(dp[i])
### BUGGY CODE ###

n = int(input())
ans = 0

for i in range(1, n):
    ans += i

print(ans)


### FIXED CODE ###

n = int(input()) - 1
print(n*(n+1)//2)
### BUGGY CODE ###

import numpy as np
n = int(input())
A = [[ord(i) for i in input()] for j in range(n)]
count = 0
for a in range(n):
    arr = np.roll(A, a, axis=0)
    if np.allclose(arr,arr.T):
        count += n
print(count)

### FIXED CODE ###

n = int(input())
A = [input() for _ in range(n)]
# AT = list(map(''.join,zip(*A)))
count = 0
for a in range(n):
    arr = A[a:][:] + A[:a][:]
    arrT = list(map(''.join, zip(*arr)))
    for i in range(n):
        if arr[i][i+1:] != arrT[i][i+1:]:
            break
    else:
        count += n
print(count)
### BUGGY CODE ###

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

for i in range(M):
    A, B = map(int, input().split())
    x = min(A, B)
    y = max(A, B)
    if [x, y] not in k:
        friend[A-1] += 1
        friend[B-1] += 1
        k.append([x, y])
    if max(friend) == N-1:
        break

print(max(friend)+1)


### FIXED CODE ###

def find(n):
    if parent[n] < 0:
        return n
    else:
        parent[n] = find(parent[n])
        return parent[n]


def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x == root_y:
        return
    if parent[root_x] > parent[root_y]:
        root_x, root_y = root_y, root_x
    parent[root_x] += parent[root_y]
    parent[root_y] = root_x


def get_size(x):
    return -parent[find(x)]


n, m = map(int, input().split())
parent = [-1 for _ in range(n)]

for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    union(a, b)
ans = 0
for i in range(n):
    ans = max(ans, get_size(i))
print(ans)
### BUGGY CODE ###

import numpy as np

def solve(S, i, Ns):
    #print("i:{}".format(i))
    #print("Ns:{}".format(Ns)) 
    if len(S) <= i:
        return 0 # Ns[i] でインデックスの外
    if Ns[i] != -1:
        return Ns[i]
    N = 0
    for j in range(i+1, len(S)+1):
        s = int(S[i:j])
        if s % 2019 == 0:
            N = 1+solve(S,i+j, Ns)
            break
    Ns[i] = N
    return N


if __name__ == "__main__":
    # 2019 = 3 * 673
    S = str(input())
    n = len(S)
    Ns = [-1 for i in range(n)]

    # ans = 0
    # # for i in range(2019):
    # #     for j in range(1, 10):
    # #         if (i*10+j) % 2019 == 0:
    # #             print(i,j)
    # # for i in range(0, n):
    # #     for j in range(i+1, n+1):
    # #         s = int(S[i:j])
    # #         #print(s)
    # #         if s % 2019 == 0:
    # #             #print("i,j : {}, {}".format(i, j))
    # #             ans += 1
    # print(ans)

    for i in range(len(S)):
        solve(S, i, Ns)
    #print(Ns)
    print(sum(Ns))




### FIXED CODE ###

import numpy as np
import collections

def main():
    S = str(input())
    n = len(S)

    T = [-1 for i in range(n+1)]
    T[-1] = 0
    # for i in range(n):
    #     #print(S[i:])
    #     T[i] = int(S[i:]) % 2019
    # print(T)
    b = [1 for i in range(n)]
    for i in reversed(range(n-1)):
        b[i] = b[i+1]*10 % 2019
    #print(b)

    # for i in reversed(range(n)):
    #     T[i] = (int(S[i])*10**(n-1 -i) + T[i+1]) % 2019
    # print(T)

    for i in reversed(range(n)):
        T[i] = (b[i]*int(S[i]) + T[i+1]) % 2019
    #print(T)


    C = collections.Counter(T)
    #print(C) # dict 型のサブクラス，Counter
    ans = 0
    for value, count in C.items():
        ans += int(count*(count-1)/2)
    print(ans)

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

import sys
# from bisect import *
# from collections import *
# from copy import deepcopy
# from heapq import *
# from itertools import *
# from math import *
# from operator import *
# from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    H,W = map(int, input().split())
    grid = [list(input().rstrip()) for _ in range(H)]
    q = []
    visited = [[False]*W for _ in range(H)]
    for y in range(H):
        for x in range(W):
            if grid[y][x] == '#':
                q.append((y,x))
                visited[y][x] = True
    ans = -1
    while q:
        ans += 1
        new_q = []
        for y,x in q:
            for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
                ny = y+dy
                nx = x+dx
                if 0<=ny<H and 0<=nx<W and not visited[ny][nx]:
                    new_q.append((ny,nx))
                    visited[ny][nx] = True
        if new_q:
            q = new_q
        else:
            break
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    H, W = map(int,input().split())
    visited = [[False]*W for _ in range(H)]
    q = []
    for y in range(H):
        S = input()
        for x, s in enumerate(S):
            if s == "#":
                q.append((y, x))
                visited[y][x] = True

    ans = -1
    while q:
        ans += 1
        nq = []
        for y, x in q:
            if 0 < x and not visited[y][x-1]:
                visited[y][x-1] = True
                nq.append((y,x-1))
            if x < W-1 and not visited[y][x+1]:
                visited[y][x+1] = True
                nq.append((y,x+1))
            if 0 < y and not visited[y-1][x]:
                visited[y-1][x] = True
                nq.append((y-1, x))
            if y < H-1 and not visited[y+1][x]:
                visited[y+1][x] = True
                nq.append((y+1,x))
        if nq:
            q = nq
        else:
            break

    print(ans)

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

n,q = map(int,input().split())
s = list(str(input()))

for i in range(q):
        t1,t2 = map(int,input().split())
        r1 = "".join(s[t1-1:t2])
        print(r1.count("AC"))

### FIXED CODE ###

n,q = map(int,input().split())
s = list(input())
c = 0
t = [0]
for i in range(1,n):
        if s[i] == "C" and s[i-1] == "A":
                c = c + 1
        t.append(c)

for i in range(q):
        t1,t2=map(int,input().split())
        print(t[t2-1]-t[t1-1])
### BUGGY CODE ###

import queue
N,M=map(int,input().split())
ans=[0] * N
q=queue.Queue()
q.put(1)

import sys
s = sys.stdin.readlines()

c=0

while c!=N-1:
  r=q.get()
  for e in s:
    L, R = map(int, e.split())
    if L==r and ans[R-1]==0 and R!=1:
      ans[R-1]=r
      q.put(R)
      c+=1
    if R==r and ans[L-1]==0 and L!=1:
      ans[L-1]=r
      q.put(L)
      c+=1
    
print("Yes")
for i in range(N-1):
  print(ans[i+1])

### FIXED CODE ###

import queue
N,M=map(int,input().split())
ans=[0] * N
q=queue.Queue()
q.put(1)

import sys
s = sys.stdin.readlines()
G=[[] for _ in range(N)]

for e in s:
  a, b = map(int, e.split())
  G[a-1].append(b)
  G[b-1].append(a)
  
c=0

while c!=N-1:
  r=q.get()
  for i in G[r-1]:
    if ans[i-1]==0 and i!=1:
      ans[i-1]=r
      q.put(i)
      c+=1

print("Yes")
for i in range(N-1):
  print(ans[i+1])
### BUGGY CODE ###

def year(x):
    return Y[x]

N, M = [int(s) for s in input().rstrip().split()]
pref = [[] for _ in range(N)]
P = []
for m in range(M):
    p, year = [int(s) for s in input().rstrip().split()]
    pref[p-1].append([year, m])
    P.append(p)

id = []    
for n in range(N):
    if pref[n]:
        pref[n].sort()

for i, p in enumerate(P):
    for j, city in enumerate(pref[p-1]):
        if city[1] == i:
            x = j+1
    id.append('{0:06d}{1:06d}'.format(p, x))

for m in range(M):
    print(id[m])

### FIXED CODE ###

N, M = [int(s) for s in input().rstrip().split()]
pref = [[] for _ in range(N)]
P = []
for m in range(M):
    p, year = [int(s) for s in input().rstrip().split()]
    pref[p-1].append([year, m])
    P.append(p)

id = [None] * M
for n, p in enumerate(pref):
    if not p:
        continue    
    p.sort()
    for x, (year, m) in enumerate(p):
        id[m] = '{0:06d}{1:06d}'.format(n+1, x+1)

print('\n'.join(id))
### BUGGY CODE ###

n,s=map(int,input().split())
a = list(map(int,input().split()))
mod = 998244353
dp = [[[0 for i in range(3)] for i in range(s+1)]for i in range(n+1)]
dp[0][0][0]=1

for i in range(1,n+1):
    for j in range(s+1):
        dp[i][j][0] += dp[i-1][j][0]
        dp[i][j][0] %= mod
        dp[i][j][1] += dp[i-1][j][1]+dp[i-1][j][0]
        dp[i][j][1] %= mod
        dp[i][j][2] += dp[i-1][j][2]+dp[i-1][j][1]+dp[i-1][j][0]
        dp[i][j][2] %= mod
        if j-a[i-1]>=0:
            dp[i][j][1] += dp[i-1][j-a[i-1]][1]+dp[i-1][j-a[i-1]][0]
            dp[i][j][1] %= mod
            dp[i][j][2] += dp[i-1][j-a[i-1]][0]+dp[i-1][j-a[i-1]][1]
            dp[i][j][2] %= mod

#tmp = [[dp[i][j][2]for j in range(s+1)]for i in range(n+1)]
#print(tmp)

print(dp[n][s][2])


### FIXED CODE ###

import sys
import math
def input():
    return sys.stdin.readline()[:-1]
n,s=map(int,input().split())
a = list(map(int,input().split()))
mod = 998244353
dp0 = [[0 for i in range(s+1)]for i in range(n+1)]
dp1 = [[0 for i in range(s+1)]for i in range(n+1)]
for i in range(1,n+1):
    for j in range(s+1):
        if j==0:
            b=1
        else:
            b=0
        dp0[i][j] += (dp0[i-1][j]+b)
        dp0[i][j] %= mod
        dp1[i][j] += (dp1[i-1][j]+dp0[i-1][j]+b)
        dp1[i][j] %= mod
        if j+a[i-1]<=s:
            dp0[i][j+a[i-1]] += (dp0[i-1][j]+b)
            dp0[i][j+a[i-1]] %= mod
            dp1[i][j+a[i-1]] += (b+dp0[i-1][j])
            dp1[i][j+a[i-1]] %= mod

        dp0[i][j]%=mod
        dp1[i][j]%=mod

print(dp1[n][s])
### BUGGY CODE ###

S=input().strip()
N=len(S)

a=[0 if x == '0' else 1 for x in S]

while True:
    v = 0
    p = -1
    b = []
    for i in a:
        if p >= 0:
            if p == 0 or p == 1:
                if i == 0 or i == 1:
                    if p != i:
                        p = -1
                        v += 1
                        continue
            b.append(p)
        p = i
    if p >= 0:
        b.append(p)
    if v == 0:
        print(N - len(a))
        break
    a = b



### FIXED CODE ###

from collections import deque
S=input().strip()
N=len(S)

a=[0 if x == '0' else 1 for x in S]

q = deque()
for i in a:
    if q:
        if q[-1] != i:
            q.pop()
        else:
            q.append(i)
    else:
        q.append(i)

print(N-len(q))
### BUGGY CODE ###

from functools import reduce
from operator import mul

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

seki = reduce(mul, l)
print(-1 if seki > 10 ** 18 else seki)

### FIXED CODE ###

from functools import reduce
from operator import mul
import math

def main():
    n = int(input())
    l = list(map(int, input().split()))

    if 0 in l:
        print(0)
        return
    l_sorted = sorted(l, reverse=True)
    log = 0
    seki = 1
    for i in l_sorted:
        log += math.log10(i)
        if log > 18:
            print(-1)
            return
        elif log == 18:
            seki *= i
            if seki != 10 ** 18:
                print(-1)
                return
        else:
            seki *= i
    print(seki)
    return


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

n = int(input())
pos = []
for _ in range(n):
    p = list(map(int, input().split()))
    pos.append(p)

ans = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        dpos = [pos[i][0] - pos[j][0], pos[i][1] - pos[j][1]]
        cnt = 0
        for k in range(n):
            for l in range(n):
                if k == l:
                    continue
                tmp = [pos[k][0] - pos[l][0], pos[k][1] - pos[l][1]]
                if dpos[0] == tmp[0] and dpos[1] == tmp[1]:
                    cnt += 1
        ans = max(cnt, ans)

print(n-ans)


### FIXED CODE ###

n = int(input())
pos = []
for _ in range(n):
    p = list(map(int, input().split()))
    pos.append(p)

ans = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        dpos = [pos[i][0] - pos[j][0], pos[i][1] - pos[j][1]]
        cnt = 0
        for k in range(n):
            for l in range(n):
                if k == l:
                    continue
                tmp = [pos[k][0] - pos[l][0], pos[k][1] - pos[l][1]]
                if dpos[0] == tmp[0] and dpos[1] == tmp[1]:
                    cnt += 1
        ans = max(cnt, ans)

print(n-ans)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()
ret = 0
for i in range(0, N-2):
    for j in range(i+1, N-1):
        ret += len([k for k in L[j+1:] if L[i]+L[j]>k])
print(ret)

### FIXED CODE ###

from bisect import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
ret = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        ret += bisect(L,L[i]+L[j]-1)-j-1
print(ret)
### BUGGY CODE ###

from heapq import heapify, heappop, heappush
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: tuple(map(int,input().split()))
N, D, A = inpl()
q = []
for _ in range(N):
    x, h = inpl()
    q.append((x, 0, h))
heapify(q)
ans = 0
d = 0
while q:
    x, s, h = heappop(q)
    if s == 0:
        h -= d
        if h <= 0:
            continue
        else:
            k = (h-1)//A + 1
            heappush(q, (x+2*D, 1, k*A))
            d += k*A
            ans += k
    else:
        d -= h
print(ans)

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
Xmax = 10**10
N, D, A = inpl()
XH = [inpl() for _ in range(N)]
XH.sort()
XH.append([Xmax,0])
ans = 0
d = 0
i = j = 0
R = []
while True:
    if j >= len(R) or XH[i][0] <= R[j][0]:
        x, h = XH[i]
        i += 1
        if x >= Xmax:
            break
        h -= d
        if h <= 0:
            continue
        else:
            k = (h-1)//A + 1
            R.append((x+2*D, k*A))
            d += k*A
            ans += k
    else:
        x, h = R[j]
        j += 1
        d -= h
print(ans)
### BUGGY CODE ###

n, m , k = map(int, input().split())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))

for i in range(1, n+1):
    a[i] += a[i-1]
for i in range(1, m+1):
    b[i] += b[i-1]

ans = 0

for a_cnt in range(n+1):
    if a[a_cnt] > k:
        continue

    b_cnt = 0
    while b_cnt < m and a[a_cnt] + b[b_cnt + 1] <= k:
        b_cnt += 1
    ans = max(ans, a_cnt+b_cnt)

print(ans)

### FIXED CODE ###

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

sa = [0] * (n+1)
sb = [0] * (m+1)
r = m
ans = 0

for i in range(n):
    sa[i+1] = sa[i] + a[i]
for i in range(m):
    sb[i+1] = sb[i] + b[i]

for i in range(n+1):
    if sa[i] > k:
        break
    while sa[i] + sb[r] > k:
        r -= 1
    ans = max(ans, i+r)
print(ans)
### BUGGY CODE ###

#coding:utf-8
import itertools
import numpy as np
# d, g = 2, 700
# ls_p = [3, 5]
# ls_c = [500, 800]
d, g = map(int,input().split())
ls_p = []
ls_c = []
for i in range(d):
    p, c = map(int,input().split())
    ls_p.append(p)
    ls_c.append(c)
ls_p = np.array(ls_p)
min = ls_p.sum()
ls_c = np.array(ls_c)
nums = [0, 1]
ls_isFull = np.array([list(i) for i in itertools.product(nums, repeat=d)])[:-1]
ls_count = ls_isFull * ls_p

w = np.arange(1,d+1) * 100
#print (ls_count.dot(w) + ls_isFull.dot(ls_c))

def get_idx(ls):
    return max(np.where(ls==0)[0])


for i in range(len(ls_count)):
    idx = get_idx(ls_isFull[i])
    for j in range(ls_p[idx]):

        score = ls_count[i].dot(w) + ls_isFull[i].dot(ls_c)
        #print ( ls_count[i], score)
        if ls_count[i].sum() >=  min:
            continue
        if (score >= g) &  (ls_count[i].sum() < min):
            min = ls_count[i].sum()
            #print (min)
            continue
        ls_count[i][idx]+=1
print (min)


### FIXED CODE ###

#coding:utf-8
import itertools
import numpy as np
# d, g = 2, 700
# ls_p = [3, 5]
# ls_c = [500, 800]
d, g = map(int,input().split())
ls_p = []
ls_c = []
for i in range(d):
    p, c = map(int,input().split())
    ls_p.append(p)
    ls_c.append(c)
ls_p = np.array(ls_p)
min = ls_p.sum()
ls_c = np.array(ls_c)
nums = [0, 1]
ls_isFull = np.array([list(i) for i in itertools.product(nums, repeat=d)])[:-1]
ls_count = ls_isFull * ls_p

w = np.arange(1,d+1) * 100
#print (ls_count.dot(w) + ls_isFull.dot(ls_c))

def get_idx(ls):
    return max(np.where(ls==0)[0])


for i in range(len(ls_count)):
    
    if ls_count[i].sum() >=  min:
        continue
    idx = get_idx(ls_isFull[i])
    for j in range(ls_p[idx]):

        score = ls_count[i].dot(w) + ls_isFull[i].dot(ls_c)
        #print ( ls_count[i], score)

        if (score >= g) &  (ls_count[i].sum() < min):
            min = ls_count[i].sum()
            #print (min)
            continue
        ls_count[i][idx]+=1
print (min)
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(n):
     ans += i
print(ans)

### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)