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

import itertools
d, g = map(int, input().split())
a = []
c = []
for i in range(d):
    a.append(list(map(int, input().split())))
itr = [i for i in range(d)]
p = list(itertools.permutations(itr, len(itr)))
for b in p:
    count = 0
    r = g
    for i in b:
        if r <= 0:
            break
        temp = (i+1) * 100
        l = [temp] * a[i][0]
        l[-1] += a[i][1]
        for j in range(len(l)):
            count += 1
            r -= l[j]
            if r <= 0:
                c.append(count)
                break
print(min(c))


### FIXED CODE ###

d, g = map(int, input().split())
a = []
c = []
for i in range(d):
    a.append(list(map(int, input().split())))
for i in range(2 ** d):
    summ = 0
    count = 0
    j = list(bin(i)[2:].zfill(len(bin(2 ** d - 1)[2:])))
    for k in range(len(j)):
        summ += int(j[k]) * a[k][0] * (k+1) * 100
        if j[k] == '1':
            count += a[k][0]
            summ += a[k][1]
    if summ >= g:
        c.append(count)
        continue
    elif summ < g:
        idx = 0
        for l in range(len(j) - 1, 0, -1):
            if j[l] == '0':
                idx = l
                break
        for m in range(1, a[idx][0]):
            summ += (idx+1) * 100
            count += 1
            if summ >= g:
                c.append(count)
                break

print(min(c))
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
s=[]
for i in range(len(p)-k+1):
  t=p[i:i+k]
  s.append(t)
#print(s)
ans=0
for i in range(len(s)):
  sums=0
  for j in range(k):
    sums+=(s[i][j]+1)*s[i][j]/2/s[i][j]
  #print(sums)
  ans=max(ans,sums)
print('{:.10f}'.format(ans))

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
s=[]
for i in p:
  t=(1+i)
  s.append(t)
  
t=[0,]
for i in range(n):
  u=t[i]+s[i]
  t.append(u)

ans=0
for i in range(n-k+1):
  ans=max(ans,t[i+k]-t[i])
  

print('{:.10f}'.format(ans/2))
### BUGGY CODE ###

from collections import deque 
n = int(input())
a = list(map(int, input().split()))
a.sort()
a = deque(a)
if a.count(min(a)) >= 2:
    ans = 0
    z = 0
else:
    ans = 1
    z = 1
ln = [i for i in a if a.count(i) >= 2]
y = [min(a)]
while a:
    v = a.popleft()
    if v not in ln:
        x = 0
        for j in y:
            if v % j == 0:
                break
            else:
                x += 1
            if x == len(y):
                ans += 1
                y.append(v)
u = [i for i in y if i not in ln]
print(len(u))

### FIXED CODE ###

from collections import Counter
import bisect
n = int(input()) #リストの要素数
a = list(map(int, input().split())) #リストの要素
cnt = Counter(a) #aの要素数についての辞書
a.sort()#aを小さい順にソート
ans = 0
mx = 10 ** 6
p = [0] * (mx + 1)
for i in a:
    if p[i] == 0:
        for j in range(mx + 1):
            x = i * j
            if x > mx:
                break
            p[x] = 1 #pの中でaの要素iの倍数として表現できるものに１
        if cnt[i] == 1:
            ans += 1 #pの中で任意のiの倍数として表現できず、かつ１つのみ存在するものをカウント
print(ans)
### BUGGY CODE ###

from collections import deque
import numpy as np
h, w = map(int, input().split())
mass = [[ord(i) for i in input()] for _ in range(h)]
wall = ord("#")

dr = np.array([[0, 1], [0, -1], [1, 0], [-1, 0]])


def bfs(s, t):
    if mass[s][t] == wall:
        return 0
    visited = np.zeros((h, w))
    depth = np.zeros((h, w))
    q1 = deque([s])
    q2 = deque([t])
    while q1:
        x = q1.popleft()
        y = q2.popleft()
        visited[x][y] += 1
        dr_i = dr + [x, y]
        for nx, ny in dr_i:
            if nx < 0 or h - 1 < nx:
                continue
            if ny < 0 or w - 1 < ny:
                continue

            if mass[nx][ny] == wall:
                continue
            if visited[nx][ny]:
                continue

            q1.append(nx)
            q2.append(ny)
            depth[nx][ny] = depth[x][y] + 1

    return np.max(depth)


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))


### FIXED CODE ###

import numpy as np
from collections import deque
h, w = map(int, input().split())
r = [list(input()) for i in range(h)]


def dist(s, t):
    if r[s][t] == "#":
        return 0
    else:
        visited = np.zeros((h, w))
        visited[s][t] += 1
        distance = np.zeros((h, w))
        q = deque([[s, t]])
        while len(q) > 0:
            i, j = q.popleft()
            d = distance[i][j] + 1
            if j != w-1:
                if r[i][j+1] == "." and not visited[i][j+1]:
                    q.append([i, j + 1])
                    visited[i][j+1] += 1
                    distance[i][j+1] += d
            if j != 0:
                if r[i][j-1] == "." and not visited[i][j-1]:
                    q.append([i, j - 1])
                    visited[i][j - 1] += 1
                    distance[i][j - 1] += d
            if i != 0:
                if r[i-1][j] == "." and not visited[i-1][j]:
                    q.append([i - 1, j])
                    visited[i-1][j] += 1
                    distance[i-1][j] += d
            if i != h-1:
                if r[i+1][j] == "." and not visited[i+1][j]:
                    q.append([i + 1, j])
                    visited[i+1][j] += 1
                    distance[i+1][j] += d
        return np.max(distance)


ans = 0
for s in range(h):
    for t in range(w):
        ans = max(ans, dist(s, t))

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

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
AB = [[int(i) for i in input().split()] for _ in range(N)]
AB.sort(reverse=True)

answer = 0
for j in range(M-1,-1,-1):
    maxB = 0
    index = -1
    for i in range(len(AB)-1,-1,-1):
        a,b = AB[i]
        if a + j <= M:
            if maxB < b:
                maxB = b
                index = i
            if i == 0:
                AB.pop(index)
                answer += maxB
        else:
            if index < 0:
                break
            else:
                AB.pop(index)
                answer += maxB
                break

print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from heapq import heappush, heappushpop

N,M = map(int,input().split())
# task[締切][価値]
tasks = [[] for _ in range(M)] 
for _ in range(N):
    a,b = map(int,input().split())
    if a <= M:
        tasks[M-a].append(b)

# 受注したバイト
q = []
# 締切=dayとなる最大の価値をqに格納
for day in range(M):
    # その日締切のバイト
    for v in tasks[day]:
        # まだ今日は受注してない
        if len(q) < day+1:
            heappush(q,v)
        else:
            heappushpop(q,v)

answer = sum(q)
print(answer)
### BUGGY CODE ###

K,S = map(int, input().split())
ans = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if (x+y+z) == S:
                ans += 1;
print(ans)

### FIXED CODE ###

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

K,X,Y = (int(x) for x in input().split())
distance = [0] *( K *(K-1))
ct = 0
for i in range(1,K+1):
    for j in range (1,K+1):
        if i < j:
            distance[ct] = min(j-i,abs(i-X)+abs(j-Y)+1)
            ct += 1
for k in range (1,K):
    print(distance.count(k))

### FIXED CODE ###

K,X,Y = (int(x) for x in input().split())
ans = [0] * K
ct = 0
for i in range(1,K):
    for j in range (i+1,K+1):
            ans[min(j-i,abs(i-X)+abs(j-Y)+1)] += 1
for k in range (1,K):
    print(ans[k])
### BUGGY CODE ###

import math
n = int(input())
list_voc = [str(input()) for _ in range(n)]
list_mo = []
for i, s in enumerate(list_voc):
    list_n = list(s)
    list_n.sort()
    list_n = ''.join(list_n)
    list_mo.append(list_n)


set_mo = set(list_mo)
list_mo_s = list(set_mo)
ans = []
for s in list_mo_s:
    ans.append(list_mo.count(s))

ans_val = []

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


for s in ans:
    if s != 1:
        ans_val.append(cmb(s, 2))


print(sum(ans_val))


### FIXED CODE ###

import math
n = int(input())
list_voc = [str(input()) for _ in range(n)]
list_mo = []
for i, s in enumerate(list_voc):
    list_n = list(s)
    list_n.sort()
    list_n = ''.join(list_n)
    list_mo.append(list_n)

ans = {}
for s in list_mo:
    if s in ans:
        ans[s] += 1
    else:
        ans[s] = 1


ans_val = []

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


for s in ans:
    if ans[s] != 1:
        ans_val.append(cmb(ans[s], 2))


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

n, m = input().split()
n = int(n)
m = int(m)
 
result_list = []
true_flag = False
for i in range(m):
    a,b=input().split()
    result_list.append((int(a), b))
    if b == "AC":
        true_flag = True
 
# 正解した問題を入れるlist
done_list = []
pn_list = [0] * n
correct = 0
pn = 0
 
if true_flag == False:
    print(0, 0)
else: 
    for result in result_list:
        if result[0] in done_list:
            pass
        elif result[1] == "WA":
            pn_list[result[0] - 1] += 1

        elif result[1] == "AC":
            done_list.append(result[0])
            correct += 1
            pn += pn_list[result[0] - 1]
        if len(done_list) == n:
            break
    
    print(correct, pn)

### FIXED CODE ###

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

# 正解した問題を入れるlist

correct = 0
pn = 0
done_list = [0] * n
pn_list = [0] * n

for i in range(m):
    a,b=input().split()
    
    if done_list[int(a)-1] == 0 and b == "AC":
        done_list[int(a)-1] += 1
        correct += 1
        pn += pn_list[int(a) - 1]
    elif b == "WA":
        pn_list[int(a) - 1] += 1

print(correct, pn)
### BUGGY CODE ###

N, Q = map(int, input().split(" "))
 
ns= [list(map(int, input().split(" ")))  for _ in range(N-1)]
 
flags = [False]*N
dic = [[] for _ in range(N)]
rlt = [0]*N
 
for i in range(N-1):
  dic[ns[i][1]-1] += [ns[i][0]-1]
  dic[ns[i][0]-1] += [ns[i][1]-1]
  
for p, x in (map(int, input().split()) for _ in range(Q)):
  rlt[p - 1] += x

que = [0]
while len(que):
  a = que.pop(0)
  flags[a] = True
  for e in dic[a]:
    if flags[e]:
      continue
    else:
      rlt[e] += rlt[a]
      que.append(e)
    
print(" ".join(map(str, rlt)))

### FIXED CODE ###

N, Q = map(int, input().split(" "))
 
ns= [list(map(int, input().split(" ")))  for _ in range(N-1)]
vs = [list(map(int, input().split(" ")))  for _ in range(Q)]

dic = [[] for _ in range(N)]
rlt = [0]*N


for i in range(N-1):
  dic[ns[i][0]-1] += [ns[i][1]-1]
  
for j in range(Q):
  rlt[vs[j][0]-1] += vs[j][1]
  
for k in range(N):
  for l in dic[k]:
    rlt[l] += rlt[k]
    
print(" ".join(map(str, rlt)))
### BUGGY CODE ###

import math
def num_divisors(n):
    num = 0
    for i in range(1, int(math.sqrt(n) + 1e-9) + 1):
        if n % i == 0:
            num += 1
            if n != i**2:
                num += 1

    return num

n = int(input())
c = 0
for i in range(1, n):
    c += num_divisors(i)
print(c)

### FIXED CODE ###

n = int(input())
def num_divisor(n):
    table = [0] * (n + 1)

    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1

    return table
print(sum(num_divisor(n-1)))
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]


def main():
    K = int(input())
    x = 0
    i = 0
    if K % 2 == 0 or K % 5 ==  0:
        print(-1)
 
    while True:
        x = (x * 10 + 7) % K
        i += 1
        if x == 0:
            print(i)
            break


    

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]


def main():
    K = int(input())
    x = 0
    i = 0
    if K % 2 == 0 or K % 5 ==  0:
        print(-1)
        exit()
    
    while True:
        x = (x * 10 + 7) % K
        i += 1
        if x == 0:
            print(i)
            break


    

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

N = int(input())
A = [int(i) for i in input().split()]
num = 0
for i in range(N):
    num += A[i]
Q = int(input())
for _ in range(Q):
    B,C = [int(i) for i in input().split()]
    for i in range(N):
        if A[i] == B:
            A[i] = C
            num += C-B
    print(num)

### FIXED CODE ###

N = int(input())
L = [int(i) for i in input().split()]
A = [0]*(1+(10**5))
num = 0
for l in L:
    A[l] += 1
    num += l
Q = int(input())
for _ in range(Q):
    B,C =[int(i) for i in input().split()]
    num += (C-B)*A[B]
    A[C] += A[B]
    A[B] = 0
    print(num)
### BUGGY CODE ###

import sys

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

def solve():
  ret = 1
  for x in A:
    ret *= x
    if ret > 1e18:
      ret += 1
  if ret > 1e18:
    ret = -1
  return ret

print(solve())

### FIXED CODE ###

import sys

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

U = 10**18
ret = 1

for x in A:
  ret *= x
  if ret > U:
    ret = U+1
    
if ret > U:
  ret = -1

print(ret)
### BUGGY CODE ###

import sys
from fractions import gcd
input = sys.stdin.readline

K = int(input())
ans = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            ans += gcd(gcd(i, j), k)

print(ans)

### FIXED CODE ###

import sys
from math import gcd
input = sys.stdin.readline

K = int(input())
ans = 0

for i in range(1, K+1):
    for j in range(i, K+1):
        for k in range(j, K+1):
            if i == j and k == i:
                ans += gcd(gcd(i, j), k)
            elif i == j or k == i or j == k:
                ans += 3 * gcd(gcd(i, j), k)
            else:
                ans += 6 * gcd(gcd(i, j), k)

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

def bfs(sx, sy, gx, gy, maze):
  INF = 10000
  distance = [[INF for i in range(W)] for j in range(H)]
  queue = []
  queue.insert(0, (sx, sy))
  distance[sy][sx] = 0
  while len(queue):
    x, y = queue.pop()
    if x == gx and y == gy:
      break
    for i in range(0, 4):
      nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
      if (0 <= nx and nx < W and 0 <= ny and ny < H and maze[ny][nx] != '#' and distance[ny][nx] == INF):
        queue.insert(0, (nx, ny))
        distance[ny][nx] = distance[y][x] + 1
  return distance[gy][gx]

H,W = (int(x) for x in input().split())
maze = ['']*H
max_distance = 0
maze = [list(input()) for _ in range(H)]

dic = {}
for i in range(H*W):
  dic[i] = [i % W,i//W,0]
  
for i in range(H*W):
  sx,sy = dic[i][0],dic[i][1]
  s = maze[sy][sx]
  if s == '#':
    continue
  for j in range(H*W):
    gx,gy = dic[j][0],dic[j][1]
    g = maze[gy][gx]
    if i == j or g == '#' or dic[j][2] == 1:
        continue
    tmp_s = s
    tmp_g = g
    maze[sy][sx] = 'S'
    maze[gy][gx] = 'G'
    max_distance = max(max_distance,bfs(sx, sy, gx, gy, maze))
    maze[sy][sx] = tmp_s
    maze[gy][gx] = tmp_g
  dic[i][2] = 1
        
print(max_distance)    

    

### FIXED CODE ###

from collections import deque
import math
import copy
H,W = map(int,input().split())
maze = [list(input()) for _ in range(H)]
def bfs(maze,h,w,sx,sy):
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                maze[y][x]=float('inf')

    maze[sy][sx]=0
    que=deque([[sy,sx]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            if 0 <= y+i < H and 0<=x+j<W:
                nexty,nextx=y+i,x+j
                dist=maze[nexty][nextx]
                if dist!='#':
                    if dist>maze[y][x]+1:
                        maze[nexty][nextx]=maze[y][x]+1
                        que.append([nexty,nextx])
    m = 0                   
    for l in maze:
      li = [i for i in l if i != '#' and i < 1000000]
      if len(li) > 0:
        m = max(m,max(li))
    return m
max_dist = -1  
for si in range(H):
  for sj in range(W):
    if maze[si][sj] == '#':
      continue
    copymaze = copy.deepcopy(maze)
    res = bfs(copymaze,H,W,sj,si)
    max_dist = max(max_dist,res)
print(max_dist)
### BUGGY CODE ###

from sys import stdin
from queue import deque


def main():
    n, x, y = [int(x) for x in stdin.readline().rstrip().split()]
    x -= 1
    y -= 1
    ans = [0] * n
    for i in range(n):
        dist = [None] * n
        q = deque()

        def push(d, v):
            if v < 0 or n <= v:
                return
            if dist[v] is not None:
                return
            dist[v] = d
            q.append(v)

        push(0, i)
        while len(q):
            v = q.popleft()
            d = dist[v]
            push(d + 1, v - 1)
            push(d + 1, v + 1)
            if v == x:
                push(d + 1, y)
            if v == y:
                push(d + 1, x)

        for d in dist:
            ans[d] += 1

    ans = [x // 2 for x in ans]
    print(*ans[1:], sep='\n')


if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import stdin


def main():
    N, X, Y = [int(x) for x in stdin.readline().rstrip().split()]
    result = [0] * (N - 1)
    for left in range(1, N):
        for right in range(left + 1, N + 1):
            if (left <= X) and (Y <= right):
                x = (X - left) + 1 + (right - Y)
            elif (left <= X) and (X <= right <= Y):
                x = (X - left) + min((right - X), (Y - right) + 1)
            elif (X <= left <= Y) and (Y <= right):
                x = min((Y - left), (left - X) + 1) + (right - Y)
            elif (X <= left <= Y) and (X <= right <= Y):
                x = min((right - left), (left - X) + (Y - right) + 1)
            else:
                x = right - left
            result[x - 1] += 1
    print(*result, sep='\n')


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

import numpy as np
import sys
input = sys.stdin.readline
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
p = np.array(p)

p_isorder = p[1:]>p[:-1]

ans = n - k + 1
no_change = False
for j in range(k-1):
    if not p_isorder[j]:
        break
else:
    no_change = True

for i in range(n-k):
    dec = False
    q = p[i:i+k+1]
    if (q.argmin()==0 and q.argmax()==k):
        ans -= 1
        dec = True
    
    for j in range(k-1):
        if not p_isorder[i+j+1]:
            break
    else:
        if no_change and not dec:
            ans -= 1
        no_change = True

print(ans)


### FIXED CODE ###

import numpy as np
import heapq

(n,k),p = [list(map(int, s.split())) for s in open(0)]

p_np = np.array(p)
p_cumsum = (p_np[1:]>p_np[:-1]).cumsum()

c = [False] * n

_min = p[:k].copy()
_max = [-x for x in p[:k]]
heapq.heapify(_min)
heapq.heapify(_max)

ans = n - k + 1
no_change = False
if p_cumsum[k-2]==k-1:
    no_change = True

for i in range(n-k):
    decrease = False
    
    heapq.heappush(_min, p[i+k])
    heapq.heappush(_max, -p[i+k])
    
    while c[_min[0]]:
        heapq.heappop(_min)
    while c[-_max[0]]:
        heapq.heappop(_max)
    
    if (_min[0]==p[i] and -_max[0]==p[i+k]):
        ans -= 1
        decrease = True
    
    c[p[i]] = True
    
    if p_cumsum[i]+k-1 == p_cumsum[i+k-1]:
        if no_change and not decrease:
            ans -= 1
        no_change = True

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

N,M=map(int,input().split())
m=0
i=1
while  M//N>=i:
    if M%i==0:
        m=i
    i=i+1
print(m)


### FIXED CODE ###

import math

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

d=[]
i=1
while math.sqrt(M)>=i:
    if M%i==0:
        d.append(i)
        if i**2!=M:
            d.append(M//i)
    i=i+1
d.sort()#Mの約数列

m=0
i=0
while  len(d)-1>=i and M//N>=d[i]:
    if  M%d[i]==0:
        m=d[i]
    i=i+1
print(m)
### BUGGY CODE ###

N = int(input())
S = input()

ls = []
for i in range(1,N-1):
  for j in range(i+1,N):
    for k in range(j+1,N+1):
      if j - i != k - j:
        ls.append((i,j,k))
        
cnt = 0
for i,j,k in ls:
  if S[i-1] != S[j-1] and S[j-1] != S[k-1] and S[k-1] != S[i-1]:
    cnt += 1

print(cnt)

### FIXED CODE ###

N = int(input())
S = input()

ans = S.count("R") * S.count("G") * S.count("B")

for i in range(1,N-1):
  for j in range(i+1,N):
    k = 2 * j - i
    if k > N:
      break
    if S[i-1] != S[j-1] and S[j-1] != S[k-1] and S[k-1] != S[i-1]:
      ans -= 1
      
print(ans)
### BUGGY CODE ###

from collections import deque

def solve(s):
    stack = deque()
    stack.append(s)
    while len(stack) > 0:
        top = stack.pop()
        if top == '':
            return 'YES'

        if top[:5] == 'dream':
            if top[5:7] == 'er':
                stack.append(top[7:])
            stack.append(top[:5])
        elif top[:5] == 'erase':
            if len(top) > 5 and top[5] == 'r':
                stack.append(top[6:])
            else:
                stack.append(top[5:])
    return 'NO'

print(solve(input()))


### FIXED CODE ###

from collections import deque

def solve(s):
    stack = deque()
    stack.append(s)
    while len(stack) > 0:
        top = stack.pop()
        if top == '':
            return 'YES'

        if top[:5] == 'dream':
            if top[5:7] == 'er':
                stack.append(top[7:])
            stack.append(top[5:])
        elif top[:5] == 'erase':
            if len(top) > 5 and top[5] == 'r':
                stack.append(top[6:])
            else:
                stack.append(top[5:])
    return 'NO'

print(solve(input()))
### BUGGY CODE ###

import copy
S=list(input())
ans=1
l=S.pop(0)
while len(S)>=1:
    x=S.pop(0)
    if l!=x:
        ans+=1
        l=copy.deepcopy(x)
    else:
        if len(S)>=1:
            ans+=1
            l=copy.deepcopy(x)+S.pop(0)
        else:
            break
print(ans)



### FIXED CODE ###

from collections import deque
import copy
S=deque(list(input()))
ans=1
l=S.popleft()
while len(S)>=1:
    x=S.popleft()
    if l!=x:
        ans+=1
        l=copy.deepcopy(x)
    else:
        if len(S)>=1:
            ans+=1
            l=copy.deepcopy(x)+S.popleft()
        else:
            break
print(ans)
### BUGGY CODE ###

a = list(input())
a.reverse()
s = [0]
ans = [1] + [0] * 2018
ans_int = 0

for i in range(len(a)):
    add = s[i] + int(a[i]) * 10 ** i
    add = add % 2019
    ans[add] += 1
    s.append(add)
    if ans[add] > 1:
        ans_int += 1


print(ans_int)

### FIXED CODE ###

a = input()[::-1]
add = 0
ans = [1] + [0] * 2018
ans_int = 0
d = 1

for i in range(len(a)):
    add = (add + int(a[i]) * d) % 2019
    d = (10 * d) %2019
    ans[add] += 1

for i in range(len(ans)):
    a =((ans[i] - 1) * ans[i]) /2
    ans_int += a

print(int(ans_int))
### BUGGY CODE ###

def resolve():
    N = int(input())
    L = list(map(int,input().split()))
    L = sorted(L,reverse=True)
    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            for k in range(N-1,j,-1):
                if L[k] + L[j] > L[i]:
                    ans += k-j
                    break
    print(ans)
resolve()

### FIXED CODE ###

def resolve():
    import bisect
    N = int(input())
    L = list(map(int,input().split()))
    L = sorted(L)
    ans = 0
    for i in range(N-1,-1,-1):
        for j in range(i-1,-1,-1):
            p = j - bisect.bisect_left(L,L[i]-L[j]+1)
            if p < 1:
                break
            ans += p
    print(ans)
resolve()