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

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate, combinations
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]



n = val()
l = []

for i in range(n):
    l.append(li())



def return_substrings(x):
    all_combnations = [sorted(l) for i in range(len(x)) for l in combinations(x, i+1)]
    return list(all_combnations)



def findans(arr):
    ans = 0

    for j in arr:
        for k in arr:
            ans += l[j][k]
    
    return ans
def givemask(arr):
    mask = 0
    for i in arr:
        mask += 1 << i
    return mask


d = {}
for i in return_substrings(range(n)):
    d[tuple(i)] = [findans(i), givemask(i)]

# print(d)


@lru_cache(None)
def dp(mask = 0):
    if mask == 2 ** n - 1:return 0


    currans = 0
    l1 = [j for j in range(n) if (mask >> j) & 1 == 0]
    l2 = []
    for iteration in return_substrings(l1):
        # curr = findans(iteration)
        # masknow = 0
        # for i in iteration:
        #     masknow += 1 << i
        curr, masknow = d[tuple(iteration)]

        currans = max(currans, curr + dp(mask + masknow))
    
    return currans


print(dp() // 2)

### FIXED CODE ###

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate, combinations
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]




n = val()
l = []

for i in range(n):
    l.append(li())


ans = [-float('inf') for i in range(2 ** n)]

ans[0] = 0

for i in range(1, 2 ** n):


    curr = 0
    for j in range(n):
        for k in range(n):
            if (i >> j) & 1 == (i >> k) & 1 == 1:curr += l[j][k]
    
    curr //= 2

    ind = i & (i - 1)

    while ind:
        curr = max(curr, ans[ind] + ans[ind ^ i])
        ind = (ind - 1) & i
    
    ans[i] = curr

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

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7


R, G, B, N = MAP()
count = 0
for i in range(N+1):
	for j in range(N+1):
		r = i
		g = j
		b = int(max(0, (N - r*R - g*G))/B)
		# print(r, g, b)
		if R*r + G*g + B*b == N:
			count += 1
print(count)


### FIXED CODE ###

import sys, re

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7


R, G, B, N = MAP()
count = 0
for i in range(N+1):
	for j in range(int((N-i*R)//G)+1):
		# print(r, g, b)
		# if R*i + G*j + B*int(max(0, (N - i*R - j*G))/B) == N:
		# 	count += 1
		if (N - i*R - j*G) % B == 0:
			count += 1
print(count)
### BUGGY CODE ###

#!/usr/bin/env python
# TLE

n, k = map(int, input().split())
L = [0 for _ in range(k)]
R = [0 for _ in range(k)]
for i in range(k):
    L[i], R[i] = map(int, input().split())
mod = 998244353

dp = [0 for _ in range(n+1)]
dp[0] = 0 
dp[1] = 1 

def cont(x, y): 
    ret = []
    for i in range(x, y+1):
        ret.append(i)
    return ret 

s = []
for i in range(k):
    s += cont(L[i], R[i])

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

print(dp[n]%mod)


### FIXED CODE ###

#!/usr/bin/env python

n, k = map(int, input().split())
L = [0 for _ in range(k)]
R = [0 for _ in range(k)]
for i in range(k):
    L[i], R[i] = map(int, input().split())
mod = 998244353

dp = [0 for _ in range(n+1)]
dp[1] = 1 
cumsum = [0 for _ in range(n+1)]
cumsum[1] = 1 

# O(NK)
for i in range(2, n+1):
    for j in range(k):
        li = i-R[j]
        ri = i-L[j]
        if ri<0: continue
        li = max(li, 1)
        dp[i] += (cumsum[ri]-cumsum[li-1])%mod
    cumsum[i] = cumsum[i-1]+dp[i]

print(dp[n]%mod)
### BUGGY CODE ###

# D - Triangles
import itertools


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

ans=0

l=list(itertools.combinations(Li,3))
for i in range(len(l)):
    a,b,c=l[i]
    if a<b+c and b<c+a and c<a+b:
        ans+=1
    else:
        pass

print(ans)


### FIXED CODE ###

# D - Triangles
import bisect

N=int(input())
Li=list(map(int,input().split()))
Li.sort()

ans=0

for i in range(N):
    for j in range (i+1,N):
        a=Li[i]+Li[j]
        t=bisect.bisect_left(Li,a)
        ans+=t-(j+1)

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

import sys
input = sys.stdin.readline

from collections import Counter
from heapq import heapify, heappush, heappop
from copy import deepcopy


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

    c = Counter(a)
    c = [-e for e in c.values()]
    heapify(c)

    k_mx = len(c)

    for k in range(1, n + 1):
        if k > k_mx:
            print(0)
            continue

        ans = -1
        cp = deepcopy(c)
        end = False
        while not end:
            ans += 1
            eat = []
            for _ in range(k):
                mn = heappop(cp)
                if mn == 0:
                    end = True
                    break
                eat.append(mn + 1)

            for e in eat:
                heappush(cp, e)

        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

from collections import Counter
from itertools import accumulate
from math import floor
from bisect import bisect_left


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

    c = Counter(a)
    c = list(c.values())

    d = Counter(c)
    d_li = [0] * (n + 1)
    for k, v in d.items():
        d_li[k] = v

    dk_acm = list(accumulate(d_li))

    kdk_acm = [0]
    for k, e in enumerate(d_li[1:], 1):
        kdk_acm.append(kdk_acm[-1] + k * e)

    def f(x):
        kdk_sm = kdk_acm[x]
        dk_sm = dk_acm[n] - dk_acm[x]

        return floor((kdk_sm + x * dk_sm) / x)

    fs = [float("inf")] + [f(x) for x in range(1, n + 1)]
    fs = fs[::-1]

    for k in range(1, n + 1):
        print(n - bisect_left(fs, k))


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

#!/usr/bin/env python3

"""
https://atcoder.jp/contests/agc029/tasks/agc029_a
"""

import sys
import re


s = sys.stdin.readline().rstrip()
s2 = ''
cnt = 0

while True:
    s = re.sub('^W+','',s)
    s = re.sub('B+$','',s)
    s2 = s.replace('BW', 'WB', 1)
    if s2 == s:
        break
    cnt += 1
    s = s2


print(cnt)

### FIXED CODE ###

#!/usr/bin/env python3

"""
https://atcoder.jp/contests/agc029/tasks/agc029_a
"""

import sys
import re


s = sys.stdin.readline().rstrip()
e = 0
n = 0

for chr in s:
    if chr == 'W':
        e += n

    if chr == 'B':
        n += 1

print(e)
### BUGGY CODE ###

import sys #追加

n=int(input())
sys.setrecursionlimit(10**6*2)

s=input()
X=int(s,2)
ans=[]

ans_memo=[0]*(10**6)
#print(ans_memo)
ans_memo[1]=1
ans_memo[2]=1

def DEF(x,cnt):
    global ans_memo
    #print(x,cnt,ans_memo)
    if x==0:
        return 0
    if x<10**6:    
        if ans_memo[x]!=0:
            return ans_memo[x]
        else:
            if x%(str(bin(x)).count("1"))==0:
                ans_memo[x]=1
                return 1
            else:
                tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
                ans_memo[x]=tmp
                return tmp
    else:
        if x%(str(bin(x)).count("1"))==0:
            return 1
        else:
            tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
            return tmp


ans=[]

for i in range(n):
    tmp=2**(n-i-1)
    tmp_num=X
    #1の時
    if tmp&tmp_num:
        tmp_num-=tmp
        #print(bin(tmp_num),n-i-1)
        ans.append(DEF(tmp_num,0))
        
    else:
        tmp_num+=tmp
        #print(bin(tmp_num),n-i-1)
        ans.append(DEF(tmp_num,0))

#print(ans_memo)

for item in ans:
    print(item)
            









### FIXED CODE ###

def popcount(x):
    return bin(x).count("1")

n=int(input())
s=input()
X=int(s,2)

one_cnt=popcount(X)

modp=X%(one_cnt+1)
modm=X%(one_cnt-1) if one_cnt-1!=0 else 0

for i in range(n):
    if s[i]=="1":
        if one_cnt-1==0:
            print(0)
            continue
        else:
            num=(modm-pow(2,n-i-1,one_cnt-1))%(one_cnt-1)
    else:
        num=(modp+pow(2,n-i-1,one_cnt+1))%(one_cnt+1)

    #print(i,"num",num)
    cnt=1
    while num!=0:
        num=num%popcount(num)
        cnt+=1
    print(cnt)
### BUGGY CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())

neighbor = defaultdict(list)
counter = [0] * N

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

for i in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x

def propagate(node, parent):
    if parent is not None:
        counter[node] += counter[parent]
    for c in neighbor[node]:
        if c != parent:
            propagate(c, node)

propagate(0, None)
print(*counter)


### FIXED CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(100000)
N, Q = map(int, input().split())

neighbor = defaultdict(list)
counter = [0] * N
pcounter = [None] * N
depth = {0: 0}

for i in range(N-1):
    a, b = map(int, input().split())
    a_deper, b_deeper = False, False
    if a in depth and b not in depth:
        depth[b] = depth[a] + 1
    if b in depth and a not in depth:
        depth[a] = depth[b] + 1
    if a in depth and b in depth:
        if depth[a] < depth[b]:
            neighbor[a-1].append(b-1)
        else:
            neighbor[b-1].append(a-1)
    else:
            neighbor[a-1].append(b-1)
            neighbor[b-1].append(a-1)

for i in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x

def solve():
    stack = [(0, None)]
    while stack:
        (node, parent) = stack.pop()
        pcounter[node] = counter[node]
        if parent is not None:
            pcounter[node] += pcounter[parent]
        for c in neighbor[node]:
            if pcounter[c] is None:
                stack.append((c, node))

solve()
print(*pcounter, sep=' ')
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2, -1, 0, 1, 2]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and visited[_h][_w] == 0 and t[_h][_w] == '.' and (not (_p) in d):
        d.append(_p)
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and visited[_h][_w] == 0 and t[_h][_w] == '.':
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()
### BUGGY CODE ###

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

list1 = []
for i in range(m):
    list1.append(int(input()))

dp = [0]*(n+1)
dp[0] = 1
if not 1 in list1: 
	dp[1] = 1 #i+2まで考えるため、初期設定はi = 1まで必要
for i in range(n-1):
	if (i in list1)and (i+1 in list1):
		break
	if i in list1 :
		dp[i+2] = dp[i+1]
	elif i+1 in list1:
		dp[i+2] = dp[i]
	else:
		dp[i+2] = dp[i] + dp[i + 1]

print(dp[n]%1000000007)



### FIXED CODE ###

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


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

for i in range(m):
	dp[int(input())] = -1

if dp[1] != -1:
	dp[1] = 1

for i in range(n-1):
	if dp[i+2] != -1:
		if dp[i+1] != -1:
			dp[i+2] += dp[i+1]
		if dp[i] != -1:
			dp[i+2] += dp[i]

print(dp[n]%1000000007)
### BUGGY CODE ###

import re

S=input()
S_int = int(S)
interval = 2019
current = 2019
#A=[]
count = 0
for i in range(len(S)):
  for j in range(i+4,len(S)+1):
    if int(S[i:j])%2019 == 0:
      #A.append([i+1,j])
      count += 1
#print(len(A))
print(count)

### FIXED CODE ###

S=input()
dp = {0:1}

p=0
q=1

for i in range(len(S)-1,-1,-1):
  p += (int(S[i])*q)
  p = p%2019
  q *= 10
  q = q%2019
  if p not in dp:
    dp[p]=0
  dp[p]+=1

#print(dp)
c = 0
for v in dp:
  c += dp[v]*(dp[v]-1)//2
print(c)
### BUGGY CODE ###

N = int(input())


def divisor(n):
    count = 0
    i = 1
    while i * i <= n:
        ans, mod = divmod(n, i)
        if mod == 0:
            if ans == i:
                count += 1
            else:
                count += 2
        i += 1
    return count

total_pair = 0

for c in range(1, N):
    y = N - c
    total_pair += divisor(y)

print(total_pair)

### FIXED CODE ###

N = int(input())
 
count = 0
for a in range(1, N):
    ans, mod = divmod(N, a)
    if mod == 0:
        count += ans - 1
    else:
        count += ans
 
print(count)
### BUGGY CODE ###

A, B, K = map(int, input().split())
big = [i for i in range(A, B+1)]
big.sort(reverse=True)
small = [i for i in range(A, B+1)]

ans = []

ans += small[:K]
ans += big[:K]

ans = list(set(ans))
ans.sort()
for i in range(len(ans)):
    print(ans[i])


### FIXED CODE ###

A, B, K = map(int, input().split())
a = A
b = B

ans = []
for i in range(K):
    if A not in ans:
        ans.append(A)

    if B not in ans:
        ans.append(B)

    if A + 1 <= b:
        A += 1
    if B - 1 >= a:
        B -= 1

ans.sort()
for i in ans:
    print(i)
### BUGGY CODE ###

N = int(input())
t = [[0 for i in range(9)] for _ in range(9)]
ans = 0
for i in range(1, 10):
    for l in range(1, 10):
        for q in range(1, N+1):
            s = 0
            if int(str(q)[0]) == i and int(str(q)[-1]) == l:
                s += 1
            t[i - 1][l - 1] += s
for i in range(1, N+1):
    a = str(i)[0]
    b = str(i)[-1]
    if b == "0":
        continue
    elif a == b:
        ans += t[int(a)-1][int(a)-1]
    else:
        ans += t[int(b)-1][int(a)-1]
print(ans)


### FIXED CODE ###

N = int(input())
t = [[0 for _ in range(9)] for l in range(9)]
ans = 0
for i in range(1, N+1):
    if len(str(i)) == 1:
        t[i-1][i-1] += 1
    elif str(i)[-1] != "0":
        t[int(str(i)[0])-1][int(str(i)[-1])-1] += 1
for i in range(1, N+1):
    a = str(i)[0]
    b = str(i)[-1]
    if b == "0":
        continue
    elif a == b:
        ans += t[(int(a)-1)][int(a)-1]
    else:
        ans += t[(int(b)-1)][int(a)-1]
print(ans)
### BUGGY CODE ###

*a, = map(int, open(0).read().split())
b = a[1]
l = []
for i in range(a[0]):
    if b in l:
        print(-1)
        exit()
    elif b == 2:
        print(i+1)
        exit()
    l += [b]
    b = a[b]

### FIXED CODE ###

*a, = map(int, open(0).read().split())
b = a[1]
l = []
for i in range(a[0]):
    if b == 2:
        print(i+1)
        exit()
    b = a[b]
print(-1)
### BUGGY CODE ###

import math

X = int(input())

ans = None

while ans is None:
  for i in range(math.ceil(abs(X)**0.5)+1):
    for j in range(math.ceil(abs(X)**0.5)+1):
      if i ** 5 - j ** 5 == X:
        ans = (i, j)
      elif (i*-1) ** 5 - j ** 5 == X:
        ans = (-i, j)
      elif i ** 5 - (j*-1) ** 5 == X:
        ans = (i, -j)
      elif (i*-1) ** 5 - (j*-1) ** 5 == X:
        ans = (-i, -j)
print(ans[0],ans[1])

### FIXED CODE ###

X = int(input())
 
ans = None
 
for i in range(120):
  for j in range(120):
    if i ** 5 - j ** 5 == X:
      ans = (i, j)
    elif (i*-1) ** 5 - j ** 5 == X:
      ans = (-i, j)
    elif i ** 5 - (j*-1) ** 5 == X:
      ans = (i, -j)
print(ans[0],ans[1])
### BUGGY CODE ###

'''
問題文
数列 a1,a2,...,anが以下の条件を満たすとき、 /\/\/\/ と呼ぶことにします。

・各 i=1,2,...,n−2について、ai=ai+2
・数列に現れる数はちょうど 2種類

偶数長の数列 v1,v2,...,vnが与えられます。 要素をいくつか書き換えることでこの数列を /\/\/\/ にしたいです。
書き換える要素の数は最小でいくつになるか求めてください。

制約
2≤n≤105
nは偶数
1≤vi≤105
viは整数
'''

n=int(input())
v=input().split()
vodd=[]
veven=[]
for i in range(n):
    if i%2:
        veven.append(int(v[i]))
    else:
        vodd.append(int(v[i]))

voddNum=[vodd[0]]
voddCnt=[0]
j=0
for i,odd in enumerate(vodd):
    if voddNum[j]!=odd:
        for k,num in enumerate(voddNum):
            if num==odd:
                j=k
                break
        else:
            j=k+1
            voddNum.append(odd)
            voddCnt.append(0)
    voddCnt[j]+=1
voddSet=list(zip(voddCnt, voddNum))
#voddSet=list(reversed(sorted(voddSet,key=lambda x:x[0])))
voddSet.sort(key=lambda x:x[0])
voddSet.reverse()
# print(vodd)
# print(voddNum)
# print(voddCnt)
# print(voddSet)


vevenNum=[veven[0]]
vevenCnt=[0]
j=0
for i,even in enumerate(veven):
    if vevenNum[j]!=even:
        for k,num in enumerate(vevenNum):
            if num==even:
                j=k
                break
        else:
            j=k+1
            vevenNum.append(even)
            vevenCnt.append(0)
    vevenCnt[j]+=1
vevenSet=list(zip(vevenCnt, vevenNum))
#vevenSet=list(reversed(sorted(vevenSet,key=lambda x:x[0])))
vevenSet.sort(key=lambda x:x[0])
vevenSet.reverse()
# print()
# print(veven)
# print(vevenNum)
# print(vevenCnt)
# print(vevenSet)


changeCnt=len(vodd)+len(veven)
if voddSet[0][1]==vevenSet[0][1]:
    if len(voddSet)==1 & len(vevenSet)==1:
        changeCnt-=len(vodd)
    elif len(voddSet)==1:
        changeCnt-=vevenSet[0][0]
    elif len(vevenSet)==1:
        changeCnt-=voddSet[0][0]
    else:
        if voddSet[1][0]>vevenSet[1][0]:
            changeCnt=changeCnt-voddSet[1][0]-vevenSet[0][0]
        else:
            changeCnt+=-voddSet[0][0]-vevenSet[1][0]
else:
    changeCnt+=-voddSet[0][0]-vevenSet[0][0]

print(changeCnt)
#'''


### FIXED CODE ###

n=int(input())
v=map(int,input().split())
vodd={-1:0}
veven={-1:0}
for i,vi in enumerate(v):
    if i%2:
        if(vi in veven):
            veven[vi]+=1
        else:
            veven[vi]=1
    else:
        if(vi in vodd):
            vodd[vi]+=1
        else:
            vodd[vi]=1
veven=list(veven.items())
veven.sort(key=lambda x:-x[1])
vodd=list(vodd.items())
vodd.sort(key=lambda x:-x[1])
if veven[0][0]==vodd[0][0]:
    a=veven[0][1]+vodd[1][1]
    b=veven[1][1]+vodd[0][1]
    changeCnt=n-a if a>b else n-b
else:
    changeCnt=n-veven[0][1]-vodd[0][1]

print(changeCnt)
### BUGGY CODE ###

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

max = 0
for i in range(n-k+1):
  s = sum(ps[i:i+k])
  if s > max:
    max = s
print((max + k) / 2)

### FIXED CODE ###

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

max = 0
for i in range(n-k+1):
  if i == 0:
    s = sum(ps[i:i+k])
  else:
    s = s - (ps[i-1] - ps[i+k-1])
  if s > max:
    max = s
print((max + k) / 2)
### BUGGY CODE ###

import heapq
def dijkstra_heap(N,S,edge):
  S = min(S,5000)
  d = [[float('inf')]*5001 for _ in range(N)] #始点0から各頂点への最短距離
  used = [[False]*5001 for _ in range(N)]
  d[0][S] = 0
  used[0][S] = True
  edgelist = []
  #edgelist : [(0,S)からの暫定(未確定)最短時間,頂点,銀貨の枚数]のリスト
  #edge[s] : sから出る枝の[重み,頂点,銀貨の枚数]のリスト
  for w,v,sil in edge[0]:
    if S+sil>=0 and S+sil<=5000:
      heapq.heappush(edgelist,[w,v,S+sil]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
  while len(edgelist):
    #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
    min_w,min_v,min_sil = heapq.heappop(edgelist)
    #min_w,min_v,min_sil : [0からの(確定)最短距離,頂点,銀貨の枚数]
    if used[min_v][min_sil]:
      continue
    d[min_v][min_sil] = min_w
    used[min_v][min_sil] = True
    for w,v,sil in edge[min_v]:
      if min_sil+sil>=0 and min_sil+sil<=5000 and not used[v][min_sil+sil]:
        heapq.heappush(edgelist,[min_w+w,v,min_sil+sil])
  return d

def solve():
  N, M, S = map(int, input().split())
  edge = [[] for _ in range(N)]
  for i in range(M):
    u,v,a,b = map(int, input().split())
    edge[u-1].append([b,v-1,-a])
    edge[v-1].append([b,u-1,-a])
  for i in range(N):
    c,d = map(int, input().split())
    edge[i].append([d,i,c])
  D = dijkstra_heap(N,S,edge)
  ans = [0]*N
  for i in range(1,N):
    ans[i] = min(D[i])
  return ans[1:]
print(*solve(),sep='\n')

### FIXED CODE ###

import heapq
def dijkstra_heap(N,S,Smax,edge):
  d = [float('inf')]*(10**4*N) #始点0から各頂点への最短距離
  used = [False]*(10**4*N)
  d[S] = 0
  used[S] = True
  edgelist = []
  #edgelist : [(0,S)からの暫定(未確定)最短時間,頂点,銀貨の枚数]のリスト
  #edge[s] : sから出る枝の[重み,頂点,銀貨の枚数]のリスト
  for w,a in edge[0]:
    v,sil = a//10**4,a%10**4
    if v==0 and S+sil<=Smax:
      heapq.heappush(edgelist,[w,a+S]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
    elif v>0 and S-sil>=0:
      heapq.heappush(edgelist,[w,v*10**4+(S-sil)]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
  while len(edgelist):
    #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
    min_w,min_a = heapq.heappop(edgelist)
    min_v,min_sil = min_a//10**4,min_a%10**4
    #min_w,min_v,min_sil : [0からの(確定)最短距離,頂点,銀貨の枚数]
    if used[min_a]:
      continue
    d[min_a] = min_w
    used[min_a] = True
    for w,a in edge[min_v]:
      v,sil = a//10**4,a%10**4
      if v==min_v and min_sil+sil<=Smax and not used[a+min_sil]:
        heapq.heappush(edgelist,[min_w+w,a+min_sil])
      elif v!=min_v and min_sil-sil>=0 and not used[v*10**4+(min_sil-sil)]:
        heapq.heappush(edgelist,[min_w+w,v*10**4+(min_sil-sil)])
  return d

def solve():
  N, M, S = map(int, input().split())
  edge = [[] for _ in range(N)]
  amax = 0
  for i in range(M):
    u,v,a,b = map(int, input().split())
    amax = max(amax,a)
    edge[u-1].append([b,(v-1)*10**4+a])
    edge[v-1].append([b,(u-1)*10**4+a])
  Smax = (N-1)*amax
  S = min(S,Smax)
  for i in range(N):
    c,d = map(int, input().split())
    edge[i].append([d,i*10**4+c])
  D = dijkstra_heap(N,S,Smax,edge)
  ans = [0]*N
  for i in range(1,N):
    ans[i] = min(D[i*10**4:(i+1)*10**4])
  return ans[1:]
print(*solve(),sep='\n')