Harryxun/stf_run huggingface dataset:
#Union Findデータ構造
class UnionFind:
    def __init__(self, n):
        #Data: 正:親要素のノード番号, 負:サイズ
        self.D = [-1 for i in range(n)]
    
    def find(self, x:int)->int:
        if self.D[x] < 0:
            return x
        else:
            self.D[x] = self.find(self.D[x])
            return self.D[x]

    
    def unite(self, x:int, y:int)->bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        else:
            if self.D[x] > self.D[y]:
                self.D[x], self.D[y] = self.D[y], self.D[x]
            else:
                pass
            self.D[x] += self.D[y]
            self.D[y] = x
            return True

    def same(self, x:int, y:int)->bool:
        return self.find(x) == self.find(y)

    def size(self, x:int)->int:
        return -self.D[self.find(x)]

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

uf = UnionFind(n)  

CF = [0] * n #Count Friend
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    CF[a] += 1
    CF[b] += 1
    uf.unite(a, b)

CBinG = [0] * n #Count Block in Group
for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.same(c, d) == True:
        CBinG[c] += 1
        CBinG[d] += 1
    else:
        pass

for i in range(n):
    ans = uf.size(i) - 1 - CF[i] - CBinG[i]
    print(ans, end=' ')



### FIXED CODE ###

import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]
    
    rks = [None] *n
    sys.setrecursionlimit(10**9)
    # r: どの連結成分に存在するかをメモするid
    def dfs(graph,s,r):
        if rks[s] is None:
            rks[s] = r
        for i in range(len(graph[s])):
            if rks[graph[s][i]-1] is not None:
                continue
            dfs(graph, graph[s][i]-1,r)

    for i in range(m):
        a,b = map(int, input().split())
        fgraph[a-1].append(b)
        fgraph[b-1].append(a)

    # print(fgraph)
    #print(bgraph)
    # 連結成分に対してid的なindexをつける
    c = -1
    for i in range(n):
        if rks[i] is None:
            c += 1
            dfs(fgraph, i, c)
    
    for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)

    counter = Counter(rks)
    for i in range(n):
        # counter[rks[i]] 連結成分のサイズ
        # len(fgraph[i]) 友達の数
        # len(bgraph[i]) 連結成分内のブロックの数
        # 1 自分
        print(counter[rks[i]] - len(fgraph[i]) - len(bgraph[i]) - 1)

if __name__ == '__main__':
    main()
n, init = map(int, input().split())
x = list(map(lambda a: abs(int(a)-init), input().split()))
def gcd(m,n):
    if n > m:
        gcd(n,m)
    elif m%n == 0:
        return n
    else:
        gcd(n,m%n)
g = x[0]
for i in range(n):
    if g == 1:
        break
    elif x[i] % g != 0:
        g = gcd(g,x[i])
print(g)


### FIXED CODE ###

n, init = map(int,input().split())
x = list(map(lambda x: abs(int(x)-init), input().split()))
g = x[0]
def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x%y)
for i in range(1,n):
    g = gcd(g,x[i])
print(g)
N = int(input())
a = [0]*N
for i in range(N):
    a[i] = int(input())
m = max(a)
a.remove(m)
n = max(a)


for i in range(N):
    if a[i] == m:
        print(n)
    else:
        print(m)

### FIXED CODE ###

N = int(input())
a = [0]*N
b = [0]*N
for i in range(N):
    a[i] = int(input())
    b[i] = a[i]
m = max(b)
b.remove(m)
n = max(b)

for i in range(N):
    if a[i] == m:
        print(n)
    else:
        print(m)
#include <bits/stdc++.h> 
using namespace std; 
typedef long long int lli;
#define MAX 100005
#define endl "\n"
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	lli n;
	cin>>n;
	lli mask = 1;
	lli temp;
	bool flag = false;
	bool fzero = false;
	for(lli i = 0; i<n; i++){
		cin>>temp;
		mask *= temp;
		if(mask < 0 || mask > 1000000000000000000){
			flag = true;
		}
		if(temp == 0)
			fzero = true;
	}
	if(fzero){
		cout<<0<<endl;
		return 1;
	}
	if(flag){
		cout<<"-1"<<endl;
		return 1;
	}
	cout<<mask<<endl;
}

### FIXED CODE ###


# number of elements 
n = int(input()) 
  
# Below line read inputs from user using map() function  
a = list(map(int,input().strip().split()))[:n] 
  
mask = 1;
flag = 0;
for num in a:
    if(num == 0):
            flag = 1
mask = 1;
flagex  = 0;
if(flag == 1):
    print(0)
else:
    for num in a:
        mask *= num;
        if(mask > 1000000000000000000):
            flagex = -1;
            break;
    if(flagex == -1):
        print(-1);
    else:
        print(mask);
import primefac

### FIXED CODE ###

import math


def get_max(n, p):
    factors = []
    counts = []

    count = 0
    while p % 2 == 0:
        count += 1
        p = p / 2

    if count > 0:
        factors.append(2)
        counts.append(count)

    for i in xrange(3, int(math.sqrt(p)) + 1, 2):
        # print i

        count = 0
        while p % i == 0:
            count += 1
            p = p / i

        if count > 0:
            factors.append(i)
            counts.append(count)

    if p > 2:
        factors.append(p)
        counts.append(1)

    if len(factors) == 0:
        return 1

    i = len(factors) - 1

    ans = 1

    while i >= 0:

        # print counts[i], n

        if counts[i] >= n:

            power = int(counts[i]/n)
            ans *= factors[i]**power

        i -= 1

    return ans

N, P = map(int, raw_input().split())
print get_max(N, P)
N = int(input())
a = []
for i in range(N):
    a.append(int(input()))

print(max(a) - min(a))


### FIXED CODE ###

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

print(max(a) - min(a))
A = [5, 2, 4, 6, 1, 3]

print(' '.join([str(item) for item in A]))
for i in range(1, N):
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key:
        A[j+1] = A[j]
        j = j - 1
    A[j+1] = key
    print(' '.join([str(item) for item in A]))

### FIXED CODE ###

N = int(input())
A = [int(s) for s in input().split()]

print(' '.join([str(item) for item in A]))
for i in range(1, N):
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key:
        A[j+1] = A[j]
        j = j - 1
    A[j+1] = key
    print(' '.join([str(item) for item in A]))
i = 0
while 1:
 x = raw_input()
 i+=1
 if x == '0':
  break
 print ('Case {}: {}'.format(i,v))
 

### FIXED CODE ###

i = 0
while 1:
    i+=1
    x = raw_input()
    if x == '0':
       break
    print ('Case {}: {}'.format(i,x))
n,m=map(int,input().split()) 
lista=[]
for i in range(m): 
	a=int(input())
	lista.append(a)

ans=1


def fb(num):
    """num番目のフィボナッチ数を返す
    """
    a, b = 1, 1
    for i in range(num):
        a, b = a + b, a
    return b
    
#print(fb(3))

if m==0:
	ans=ans*fb(n)
	
else:
	for i in range(m-1):
		if (lista[i]+1==lista[i+1])&(m>=2):
			ans=0
  	
  	
		else:
			lista.append(n)
			if lista[0]!=1:
					ans=ans*(fb(lista[0]-1))
					for i in range(1,m):
							ans=ans*(fb(lista[i]-lista[i-1]-2))
					
		 
					
			if lista[0]==1:
					for i in range(1,m):
							ans=ans*(fb(lista[i]-lista[i-1]-2))
					
		
	ans= ans*(fb(lista[m]-lista[m-1]-1))
		
print(ans%1000000007)
	

### FIXED CODE ###

n,m=map(int,input().split()) 
lista=[]
for i in range(m): 
	a=int(input())
	lista.append(a)

ans=1


def fb(num):
    """num番目のフィボナッチ数を返す
    """
    a, b = 1, 1
    for i in range(num):
        a, b = a + b, a
    return b
    
#print(fb(3))

if m==0:
	ans=ans*fb(n)
	
else:
	for i in range(m-1):
		if (lista[i]+1==lista[i+1])&(m>=2):
			ans=0
  	
  	
	else:
		lista.append(n)
		if lista[0]!=1:
				ans=ans*(fb(lista[0]-1))
				for i in range(1,m):
						ans=ans*(fb(lista[i]-lista[i-1]-2))
					
		 
					
		if lista[0]==1:
				for i in range(1,m):
						ans=ans*(fb(lista[i]-lista[i-1]-2))
					
		
		ans= ans*(fb(lista[m]-lista[m-1]-1))
		
print(ans%1000000007)
n, k = map(int, input().split())
li = list(map(int, input().split()))
li.append(0)
li.sort()
zero_index = li.index(0)
if zero_index == 0:
    print(li[k])
elif zero_index == len(li) -1:
    print(abs(li[-k-1]))
else:
    near_zero_small = li[zero_index-1]
    near_zero_big = li[zero_index+1]
    li.pop(zero_index)
    ans = 0
    cost = 0
    for i in range(n):
        minimam = li[i]
        maximam = li[i+k-1]
        if (minimam > 0 and maximam > 0 ):
            if minimam == near_zero_big:
                cost = maximam
        elif (minimam < 0 and maximam < 0 ):
            if minimam == near_zero_big:
                cost = abs(minimam)
        else:
            cost = min(abs(minimam), maximam)*2 + max(abs(minimam), maximam)
        if ans > cost or ans == 0:
            ans = cost
    print(ans)

### FIXED CODE ###


n, k = map(int, input().split())
li = list(map(int, input().split()))
li.append(0)
li.sort()
zero_index = li.index(0)
if zero_index == 0:
    print(li[k])
elif zero_index == len(li) -1:
    print(abs(li[-k-1]))
else:
    near_zero_small = li[zero_index-1]
    near_zero_big = li[zero_index+1]
    li.pop(zero_index)
    ans = 0
    cost = 0
    for i in range(n-k+1):
        minimam = li[i]
        maximam = li[i+k-1]
        if (minimam > 0 and maximam > 0 ):
            if minimam == near_zero_big:
                cost = maximam
        elif (minimam < 0 and maximam < 0 ):
            if minimam == near_zero_big:
                cost = abs(minimam)
        else:
            cost = min(abs(minimam), maximam)*2 + max(abs(minimam), maximam)
        if ans > cost or ans == 0:
            ans = cost
    print(ans)
N,D = map(int,input().split())
i = 0
k = 0
while N != i :
    x,y = map(int,input().split()) 
    d = (x**2+y**2) / D**2
    if d <= 1 :
        k += 1
    i +=1
print(k)

### FIXED CODE ###

N,D = map(int,input().split())
i = 0
k = 0
while N != i :
    x,y = map(int,input().split()) 
    if (x**2+y**2) <= D**2 :
        k += 1
    i +=1
print(k)
a,b,c = map(int,Input().split())



### FIXED CODE ###

a, b, c = map(int, input().split())
ans = 0
for i in range(a, b + 1):
	if c % i == 0:
		ans = ans + 1
print(ans)
# -*- coding: utf-8 -*-
n = int(input())

res1 = 0
res2 = 0
for _ in range(n):
    x,u = input().split()
    if u=="JPY":
        res1 += int(x)
    else:
        res2 += float(x)*380000.0

print("{:.8}".format(res1+res2))


### FIXED CODE ###

# -*- coding: utf-8 -*-
from decimal import *
n = int(input())

res1 = Decimal(0)
res2 = Decimal(0)
for _ in range(n):
    x,u = input().split()
    if u=="JPY":
        res1 += Decimal(x)
    else:
        res2 += Decimal(x)*Decimal(380000.0)

print(res1+res2)
N,M = map(int,input().split())
if N == M:
  print('Yes')
else:
  pritn('No')

### FIXED CODE ###

N,M = map(int,input().split())
if N == M:
  print('Yes')
else:
  print('No')
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
hand = []
for _ in range(m):
    b, c = map(int, input().split())
    hand.append((b, c))
hand.sort(key=lambda x: x[1], reverse=True)

i = 0
flag = False
for h in hand:
    for j in range(h[0]):
        if a[i] >= h[1]:
            flag = True
            break
        else:
            a[i] = h[1]
            i += 1
    if flag:
        break

print(sum(a))


### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
hand = []
for _ in range(m):
    b, c = map(int, input().split())
    hand.append((b, c))
hand.sort(key=lambda x: x[1], reverse=True)

i = 0
lena = len(a)
flag = False
for h in hand:
    for j in range(h[0]):
        if i >= lena:
            flag = True
            break
        if a[i] >= h[1]:
            flag = True
            break
        else:
            a[i] = h[1]
            i += 1
    if flag:
        break

print(sum(a))
a,b,c = map(int, input().split())
print(c) if a*c=<b else print(b//a)

### FIXED CODE ###

a,b,c = map(int, input().split())
print(c) if a*c<=b else print(b//a)
from collections import defaultdict

pc_memo = defaultdict(int)
memo = defaultdict(int)


def to_next(x):
    if x not in pc_memo.keys():
        pc_memo[x] = x % "{:b}".format(x).count('1')
    return pc_memo[x]


def f(x):
    if x == 0:
        return 0
    if x not in memo.keys():
        memo[x] = f(to_next(x))+1
    return memo[x]


for i in range(2*10**5):
    f(i)

    
n = int(input())
x = input()
one_cnt = x.count('1')

mod_minus = 0
mod_plus = 0
for i, a in enumerate(reversed(x)):
    if a == '1':
        mod_minus += pow(2, i, one_cnt-1)
        mod_minus %= one_cnt-1
        mod_plus += pow(2, i, one_cnt+1)
        mod_plus %= one_cnt+1


for i in range(n):
    if x[i] == '0':
        nx = mod_plus+pow(2, n-i-1, one_cnt+1)
        nx %= one_cnt+1
        print(f(nx)+1)
    else:
        nx = mod_minus-pow(2, n-i-1, one_cnt-1)
        nx %= one_cnt-1
        print(f(nx)+1)


### FIXED CODE ###

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

pc_memo = defaultdict(int)
memo = defaultdict(int)


def to_next(x):
    if x not in pc_memo.keys():
        pc_memo[x] = x % "{:b}".format(x).count('1')
    return pc_memo[x]


def f(x):
    if x == 0:
        return 0
    if x not in memo.keys():
        memo[x] = f(to_next(x))+1
    return memo[x]


for i in range(2*10**5):
    f(i)

n = int(input())
x = input().rstrip()
one_cnt = x.count('1')

mod_minus = 0
mod_plus = 0
for i, a in enumerate(reversed(x)):
    if a == '1':
        if 0 < one_cnt-1:
            mod_minus += pow(2, i, one_cnt-1)
            mod_minus %= one_cnt-1
        mod_plus += pow(2, i, one_cnt+1)
        mod_plus %= one_cnt+1


for i in range(n):
    if x[i] == '0':
        nx = mod_plus+pow(2, n-i-1, one_cnt+1)
        nx %= one_cnt+1
        print(f(nx)+1)
    else:
        if 0 < one_cnt-1:
            nx = mod_minus-pow(2, n-i-1, one_cnt-1)
            nx %= one_cnt-1
            print(f(nx)+1)
        else:
            print(0)
n=int(input())
a=map(int,input().split())
b=0
for_in range(a):
	for i in range(n-1,0,-1):
		if a[i]<a[i-1]:
			a[i],a[i-1]=a[i-1],a[i]
			b=b+1
print(*a)
print(b)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=0
for _ in a:
    for i in range(n-1,0,-1):
        if a[i]<a[i-1]:
            a[i],a[i-1]=a[i-1],a[i]
            b+=1
print(*a)
print(b)
N = int(input())
Xs = [list(map(int, input().split(" "))) for _ in range(N)]
"""
input = ["2 3 5","2 1 5","1 2 5","3 2 5"]
input = ["0 0 100", "1 1 98"]
input = ["99 1 191", "100 1 192", "99 0 192"]
Xs = [list(map(int, x.split(" "))) for x in input]
"""

Xs.sort(key=lambda x:x[2], reverse=True)


def solv(Xs):
    for x in range(101):
        for y in range(101):
            Cx, Cy, h = tuple(Xs)
            H = h + abs(x - Cx) + abs(y - Cy)
            for Cx, Cy, h in Xs:
                if max(H - abs(x - Cx) - abs(y - Cy), 0) != h:
                    break
            else:
                return (x, y, H)


print("%d %d %d" % solv(Xs))


### FIXED CODE ###

N = int(input())
Xs = [list(map(int, input().split(" "))) for _ in range(N)]
"""
input = ["2 3 5","2 1 5","1 2 5","3 2 5"]
input = ["0 0 100", "1 1 98"]
input = ["99 1 191", "100 1 192", "99 0 192"]
Xs = [list(map(int, x.split(" "))) for x in input]
"""

Xs.sort(key=lambda x:x[2], reverse=True)


def solv(Xs):
    for x in range(101):
        for y in range(101):
            h= Xs[0][2]
            Cx = Xs[0][0]
            Cy = Xs[0][1]
            H = h + abs(x - Cx) + abs(y - Cy)
            for i in range(len(Xs)):
                h = max(H - abs(x - Xs[i][0]) - abs(y - Xs[i][1]), 0)
                if h != Xs[i][2]:
                    break
                if i == len(Xs)-1:
                    print("%d %d %d" % (x, y, H))
                    exit(0)


solv(Xs)
import math
a = [map(int, input().split())]
print(math.ceil(sum(a)))

### FIXED CODE ###

import math
a = list(map(int, input().split()))
print(math.ceil(sum(a)/2))
import sys
import copy



S = input()
op_list = ["+"]*(len(S)-1)

sum = 0
for i in range(2**len(op_list)):

    for j in range(len(op_list)):

        if (i >> j) & 1:
            op_list[j] = ""
    s = ""
    for k in range(len(op_list)):
        s = s + S[k] + op_list[k]
    sum = sum + eval(s)


print(sum)
    




### FIXED CODE ###

import sys
import copy



S = input()
op_list = ["+"]*(len(S)-1)

sum = 0
for i in range(2**len(op_list)):
    op_list = ["+"]*(len(S)-1)
    for j in range(len(op_list)):

        if (i >> j) & 1:
            op_list[j] = ""
    s = ""
    for k in range(len(op_list)):
        s = s + S[k] + op_list[k]
    s = s + S[len(S)-1]
    sum = sum + eval(s)


print(sum)
a,b,c = map(int,input().split())

def search(a,b,c):
    lst = [0,0,0]
    if a%2 == b%2:
        lst = [1,1,0]
        if a%2==c%2:
            lst = [1,1,1]
    elif a%2 == c%2:
        lst = [1,0,1]
    else:
        lst = [0,1,1]
    return lst


def make(a,b,c):
    lst = [a,b,c]
    lst.sort()
    lst[0] += 2
    return lst[0],lst[1],lst[2]

if __name__ == "__main__":
    ans = 0
    l = search(a,b,c)
    if sum(l) == 3:
        pass
    else:
        ans += 1
        a += l[0]
        b += l[1]
        c += l[2]
    while a != b or a != c:
        a,b,c = make(a,b,c)
        ans += 1
    print(ans)

### FIXED CODE ###

lst1 = list(input())
if len(lst1) != 3:
    print("No")
    exit()
for i in ["a","b","c"]:
    if not i in lst1:
        print("No")
        exit()
print("Yes")
n = map(int, input().split())
ans = n.count('1')

print(ans)


### FIXED CODE ###

s = list(input())

ans = 0

for i in s:
    if i == '1':
        ans += 1
    
    if i == '0':
        continue

print(ans)
tmp = input()
N = int(input().split(' ')[0])
M = int(input().split(' ')[1])
C = int(input().split(' ')[2])
B = [int(b) for b in input().split(' ')]
cnt = 0
for i in range(N):
  A = [int(a) for a in input().split(' ')]
  sum = 0
  for j in range(M):
    sum += B[j]*A[j]
  sum += C
  if C > 0:
    cnt += 1
print(cnt)

### FIXED CODE ###

tmp = input()
N = int(tmp.split(' ')[0])
M = int(tmp.split(' ')[1])
C = int(tmp.split(' ')[2])
B = [int(b) for b in input().split(' ')]
cnt = 0
for i in range(N):
  A = [int(a) for a in input().split(' ')]
  sum = C
  for j in range(M):
    sum += B[j]*A[j]
  if sum > 0:
    cnt += 1
print(cnt)
x = int(input())
if x => 30:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

x = int(input())
if x >= 30:
  print("Yes")
else:
  print("No")
s = input()
s[3] = "8"
print(s)

### FIXED CODE ###

s = input()

print("2018/01/" + s[-2:])
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [set() for _ in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    G[A].add(B)
    G[B].add(A)
if M % 2 == 1:
    print(-1)
    exit()
G2 = [set() for _ in range(N+1)]
parent = [0] * (N+1)
depth = [-1] * (N+1)
depth[1] = 0
stack = [1]
while stack:
    v = stack.pop()
    if len(G[v]) == 0:
        continue
    if parent[v] != 0:
        depth[v] = depth[parent[v]] + 1
    for c in G[v]:
        G2[v].add(c)
        parent[c] = v
        G[c].remove(v)
        stack.append(c)
nodes = sorted(list(range(1, N+1)), key=lambda v: -depth[v])
ans = []
for v in nodes:
    for c in G2[v]:
        ans.append((v, c))
    if len(G2[v]) % 2 == 1:
        p = parent[v]
        ans.append((v, p))
        G2[p].remove(v)
for u, v in ans:
    print(u, v)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [set() for _ in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    G[A].add(B)
    G[B].add(A)
if M % 2 == 1:
    print(-1)
    exit()
G2 = [set() for _ in range(N+1)]
parent = [0] * (N+1)
depth = [-1] * (N+1)
depth[1] = 0
stack = [1]
while stack:
    v = stack.pop()
    if len(G[v]) > 0 and v != 1:
        depth[v] = depth[parent[v]] + 1
    for c in G[v]:
        G2[v].add(c)
        parent[c] = v
        if v in G[c]:
            G[c].remove(v)
        stack.append(c)
    G[v] = set()
nodes = sorted(list(range(1, N+1)), key=lambda v: -depth[v])
ans = []
for v in nodes:
    for c in G2[v]:
        ans.append((v, c))
    if len(G2[v]) % 2 == 1:
        p = parent[v]
        ans.append((v, p))
        G2[p].remove(v)
for u, v in ans:
    print(u, v)
a,_,_,_,e,k=[int(input()) for i in range(6)]
print(":(" if e-a>ks else "Yay!")


### FIXED CODE ###

a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
k=int(input())

m=e-a
if m>k:
  print(":(")
else:
  print("Yay!")
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, w = list(map(int, readline().split()))
    wv = [list(map(int, readline().split())) for _ in range(n)]
    dp = [0] * (w + 1)
    for ww, vv in wv:
        for i in range(w-ww+1, -1, -1):
            if i + ww <= w:
                dp[i+ww] = max(dp[i+ww], dp[i] + vv)
    print(dp[-1])


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, w = list(map(int, readline().split()))
    wv = [list(map(int, readline().split())) for _ in range(n)]
    dp = [10 ** 10] * (10 ** 3 * n + 1)
    dp[0] = 0
    max_v = 0
    for ww, vv in wv:
        for i in range(max_v, -1, -1):
            dp[i+vv] = min(dp[i+vv], dp[i] + ww)
            max_v = max(max_v, i+vv)
    mt = 0
    for i in range(len(dp)):
        if dp[i] <= w:
            mt = max(mt, i)
    print(mt)


if __name__ == '__main__':
    solve()
N = int(input())
l = list(map(int,input().split()))

data = [0]*(10001)
for i in l:
  data[i-1] += 1
  data[i] += 1
  data[i+1] += 1

print(max(data))

### FIXED CODE ###

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

data = [0]*(100010)
for i in l:
  data[i-1] += 1
  data[i] += 1
  data[i+1] += 1

print(max(data))
n, m = map(int, input().split())

friend_list = [set()]
input_list = []

for i in range(m):
    a, b = map(int, input().split())
    input_list.append([sorted([a, b])])

sorted(input_list)

for inp in input_list:
    found = False
    for friend_set in friend_list:
        if inp[0] in friend_set:
            friend_set.add(b)
            found = True
            break
        # elif b in friend_set:
        #     friend_set.add(a)
        #     found = True
        #     break
    if not found:
        friend_set = set()
        friend_set.add(a)
        friend_set.add(b)
        friend_list.append(friend_set)

ans = 0
for friend_set in friend_list:
    ans = max(len(friend_set), ans)

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

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

root = [-1] * n


def r(x):
    if root[x] < 0:
        return x
    else:
        root[x] = r(root[x])
        return root[x]


def unite(x, y):
    x = r(x)
    y = r(y)
    if x == y:
        return
    root[x] += root[y]
    root[y] = x


def size(x):
    return -1 * root[r(x)]


for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    unite(a, b)

ans = 0
for i in range(n):
    ans = max(ans, size(i))

print(ans)
import collections

n=int(input())
l=[]
for _ in range(n):
    l.append(input())

c=collections.Counter(l)
ccc=[]
for j in cc:
    if j[1]==max(c.values()):
        ccc.append(j[0])

for k in sorted(ccc):
    print(k)

### FIXED CODE ###

import collections

n=int(input())
l=[]
for _ in range(n):
    l.append(input())

c=collections.Counter(l)
cc=c.most_common()
ccc=[]
for j in cc:
    if j[1]==cc[0][1]:
        ccc.append(j[0])

for k in sorted(ccc):
    print(k)
import math
a,b,c = map(float, raw_input().split())
cc = math.radians(c)
h = b * math.sin(cc)
S = a * h / 2
L = a + b + math.sqrt(h**2 + (a-b*math.cos(cc))**2)
print("{0:.5f}\n{1:.5f}\n{2:.5f}\n".format(S, L, h))

### FIXED CODE ###

import math
a,b,c = map(float, input().split())
cc = math.radians(c)
h = b * math.sin(cc)
S = a * h / 2
L = a + b + math.sqrt(h**2 + (a-b*math.cos(cc))**2)
print("{0:.10f}\n{1:.10f}\n{2:.10f}\n".format(S, L, h))