Harryxun/stf_run huggingface dataset:
N,M = map(int,input().split())
pos=["-"]*N
if M==0:
  print("Yes")
  exit()
else:
  l,r,d=map(int,input().split())
pos[l-1]=0
pos[r-1]=pos[l-1]+d
for i in range(1,M):
  l,r,d=map(int,input().split())
  if pos[r-1]=="-":
    pos[r-1] = pos[l-1]+d
  elif pos[r-1]==pos[l-1]+d:
    continue
  else:
    print("No")
    exit()
print("Yes")

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N,M = map(int,input().split())
G = [[] for _ in [0]*N]

for _ in [0]*M:
  a, b, d = map(int, input().split())
  a -= 1
  b -= 1
  G[a].append((b, d))
  G[b].append((a, -d))

X = [None]*N

def dfs(i, x=0):
  for j, d in G[i]:
    if X[j] is None:
      X[j] = x+d
      dfs(j, x+d)
    elif X[j] != x+d:
      print('No')
      exit()

for i in range(N):
  if X[i] is not None:
    continue
  X[i] = 0
  dfs(i)
print('Yes')
from sys import stdin

S = int(stdin.readline().rstrip())

if S=="ABC":
    print("ARC")
else:
    print("ABC")



### FIXED CODE ###

from sys import stdin

S = stdin.readline().rstrip()

if S=="ABC":
    print("ARC")
else:
    print("ABC")
n = int(input())

g = [[] * 1 for i in range(n)]

for i in range(n-1):
    a = int(input())
    g[a-1].append(i+1)

def dfs(v):
    max = 0
    max_i = 0
    for u in g[v]:
        next = dfs(u)
        if next == max:
            max_i += 1
        elif next > max:
            max = next
            max_i = 1
    return max + max_i

print(dfs(0))



### FIXED CODE ###

import sys
sys.setrecursionlimit(3000000)

n = int(input())

g = [[] * 1 for i in range(n)]

for i in range(n-1):
    a = int(input())
    g[a-1].append(i+1)

def dfs(v):
    childs = []
    for u in g[v]:
        child = dfs(u)
        childs.append(child)
    childs.sort()
    ans = 1
    for child in childs:
        if ans < child:
            ans = child
        ans += 1
    return ans

print(dfs(0)-1)
k = int(input())
a, b = map(int, input().split())

if b%k == 0: 
  print(“OK”)
else:
  tmp = b//k
  tmp *= k
  if tmp>=a:
    print("OK")
  else:
    print("NG")

### FIXED CODE ###

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

if b%k == 0: 
  print("OK")
else:
  tmp = b//k
  tmp *= k
  if tmp>=a:
    print("OK")
  else:
    print("NG")
def baisu(x,a):
    if x%a ==0:
        return int(x//a)
    else:
        x -=1
        return baisu(x,a)

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

to_a = a - baisu(a,c) - baisu(a,d) + baisu(a,c*d)
to_b = b - baisu(b,c) - baisu(b,d) + baisu(b,c*d)

print(int(to_b -to_a))


### FIXED CODE ###

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def baisu(x,a):
    return int(x//a)
a,b,c,d = map(int,input().split())

to_a = a-1 - baisu(a-1,c) - baisu(a-1,d) + baisu(a-1,c*d//gcd(c,d))
to_b = b - baisu(b,c) - baisu(b,d) + baisu(b,c*d//gcd(c,d))

print(to_b - to_a)
import sys

def split(g, n):
  gl = g[:-1]
  gr = g[1:]
  sub = [[(b - a), i+1] for a, b, i in zip(gl, gr, range(len(gl)))]
  sub = sorted(sub, key = lambda x: -x[0])
  j = []
  for i in range(n-1):
    j.append(sub[i][1])
  j = sorted(j)
  jl = [0] + j[:-1]
  res = []
  for l, r in zip(jl, j):
    s = g[l:r]
    res.append(s)
  L = j[-1]
  res.append(g[L:])
  return res


def main():
  input = sys.stdin.readline
  N, M = map(int, input().split())
  g = [int(a) for a in input().split()]
  g = sorted(g)
  ans = 0
  if N < M:
    sp = split(g, N)
    for s in sp:
      if len(s) <= 0:
        continue
      ans += s[-1] - s[0]
  print(ans)


if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys

def main():
  input = sys.stdin.readline
  N, M = map(int, input().split())
  ans = 0
  if N < M:
    g = [int(a) for a in input().split()]
    g = sorted(g)
    L = g[:-1]
    R = g[1:]
    sub = [b - a for a, b in zip(L, R)]
    sub = sorted(sub)
    ans = sum(sub[:(M-N)])
  print(ans)


if __name__ == '__main__':
  main()
N, M = [int(i) for i in input().strip().split(' ')]

a = {}
b = {}
for i in range(M):
  X, Y, Z = [int(i) for i in input().strip().split(' ')]
  if X not in a:
    a[X] = set()
    b[X] = 0
  if Y not in a:
    a[Y] = set()
    b[Y] = 0

  a[X].add(Y)
  b[X] += 1
  a[Y].add(X)
  b[Y] += 1

b = sorted(list(b.items()), key=lambda e: e[1], reverse=True)

def make_keys(keys, key):
  if key in keys:
    return
  keys.add(key)
  if key in a:
    for k in a[key]:
      make_keys(keys, k)


counter = 0
# print(b)
for key, v in b:
  if key not in a:
    continue
  keys = set()
  make_keys(keys, key)

  for k in keys:
    if k in a:
      del a[k]

  counter += 1

print(counter + N - len(b))

### FIXED CODE ###

N, M = [int(i) for i in input().strip().split(' ')]

a = {}
for i in range(M):
  X, Y, _ = [int(i) for i in input().strip().split(' ')]
  if X not in a: a[X] = set()
  if Y not in a: a[Y] = set()
  a[X].add(Y)
  a[Y].add(X)

len_a = len(a)


def test(key_set):
  tmp = set()
  for key in key_set:
    if key in a:
      tmp = tmp.union(a[key])
      del a[key]

  #print('key_set = {}, tmp = {}'.format(key_set, tmp))
  return tmp


counter = 0
# print(b)

while len(a) > 0:
  #print('---')
  #print('a = {}'.format(a))
  key, key_set = a.popitem()
  #print('key = {}, key_set = {}'.format(key, key_set))
  tmp = test(key_set)
  while len(tmp) > 0:
    tmp = test(tmp)
  #print('a = {}'.format(a))
  counter += 1

print(counter + N - len_a)
n, k = map(int, input().split())

print(min(n % k), (k - (n % k)))


### FIXED CODE ###

n,k = map(int, input().split())
print(min(n % k , k - (n % k)))
a,b = input().split()
c = a*b
if type(c) == int:
    s = c
s,t =c.split('.')
print(s)

### FIXED CODE ###

from decimal import Decimal
a,b = input().split()
c = int(a)*Decimal(b)
print(int(c))
N,X =[int(i) for i in input().split()]
c = [int(i) for i in input().split()]

c.append(X)
c.sort()

D = float('inf')

for i in range(1,N+1):
    if c[i] - c[i-1] < D:
        D = abs(c[i] - c[i-1])

print(int(D))

### FIXED CODE ###

a,b=[int(i) for i in input().split()]

res = 0
f = False
for i in range(1,4):
    res = a * b * i
    if res % 2 == 1:
        f = True

if f:
    print('Yes')
else:
    print('No')
import sys
import numpy as np
 
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
 
k,x=map(int,input(),.split())

if k*500>=x:
	print("Yes")
else:
	print("No")

### FIXED CODE ###

import sys
import numpy as np
 
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
 
k,x=map(int,input().split())

if k*500>=x:
	print("Yes")
else:
	print("No")
# -*- coding: utf-8 -*-

# input & solve
N, Q = map(int, input().split())

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

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

def dfs(v, p=-1):
    for u in to[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)

dfs(0)

# output
print(*ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10 ** 7)

# input & solve
input = sys.stdin.readline
N, Q = map(int, input().split())

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

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

def dfs(v, p=-1):
    for u in to[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)

dfs(0)

# output
print(*ans)
h,w = map(int,input().split())
s =[input() for i in range(h)]


for i in range(h):
  for j in range(w):
    count = 0 
    if s[i][j]==".":
      for k in [[0,1],[1,0],[-1,0],[0,-1],[1,1],[-1,-1],[1,-1],[-1,1]]:
        if 0<=k[0]+i<h and  0<=k[1]+j<w:
          if s[k[0]+i][k[1]+j]=="#":
            count = count +1
      s[i] = s[i][0:j]+str(count)+s[i][j+1:w]
      
for i in range(h):
  for j in range(w):
    print(s[i][j], end="")
  h,w = map(int,input().split())
s =[input() for i in range(h)]


for i in range(h):
  for j in range(w):
    count = 0 
    if s[i][j]==".":
      for k in [[0,1],[1,0],[-1,0],[0,-1],[1,1],[-1,-1],[1,-1],[-1,1]]:
        if 0<=k[0]+i<h and  0<=k[1]+j<w:
          if s[k[0]+i][k[1]+j]=="#":
            count = count +1
      s[i] = s[i][0:j]+str(count)+s[i][j+1:w]
      
for i in range(h):
  for j in range(w):
    print(s[i][j], end="")
  h,w = map(int,input().split())
s =[input() for i in range(h)]


for i in range(h):
  for j in range(w):
    count = 0 
    if s[i][j]==".":
      for k in [[0,1],[1,0],[-1,0],[0,-1],[1,1],[-1,-1],[1,-1],[-1,1]]:
        if 0<=k[0]+i<h and  0<=k[1]+j<w:
          if s[k[0]+i][k[1]+j]=="#":
            count = count +1
      s[i] = s[i][0:j]+str(count)+s[i][j+1:w]
      
for i in range(h):
  for j in range(w):
    print(s[i][j], end="")
  print()

### FIXED CODE ###

h,w = map(int,input().split())
s =[input() for i in range(h)]


for i in range(h):
  for j in range(w):
    count = 0 
    if s[i][j]==".":
      for k in [[0,1],[1,0],[-1,0],[0,-1],[1,1],[-1,-1],[1,-1],[-1,1]]:
        if 0<=k[0]+i<h and  0<=k[1]+j<w:
          if s[k[0]+i][k[1]+j]=="#":
            count = count +1
      s[i] = s[i][0:j]+str(count)+s[i][j+1:w]
      
for i in range(h):
  for j in range(w):
    print(s[i][j], end="")
  print()
W, H, x, y = map(int, input().split())
# ansx = min([(W-x)*H,x*H])
# ansy = min([(H-y)*W,y*W])
if W/2 == y or H/2 == x or (W%x ==0 and H%y==0):
    print(W*H//2,1)
else:
    # print(max(ansx,ansy),0)
    print(W*H//2,0)

### FIXED CODE ###

W, H, x, y = map(float, input().split())
if x == W/2 and y == H/2:
    print(W*H/2,1)
else:
    print(W*H/2,0)
A,B=(int(i) for i in input().split())
2.if B%A==0:
3.  print(A+B)
4.else:
5.  print(B-A)


### FIXED CODE ###

A,B=(int(i) for i in input().split())
if B%A==0:
  print(A+B)
else:
  print(B-A)
x = int(input())

a = 100
i = 0

while a < X:
  
  i+ = a
  a+ = 1
print(a)
  



### FIXED CODE ###

x = int(input())

a = 100
i = 0

while a < x:
  i += 1
  a += a // 100
  
  
print(i)
a,b=[int(x) for x in input().split()]
if a > b:
 print('{0} > {1}'.format(a,b))
else if a = b:
 print('{0} == {1}'.format(a,b))
else:
 print('{0} < {1}'.format(a,b))


### FIXED CODE ###

a,b=[int(x) for x in input().split()]
if a > b:
 print('a > b')
elif a == b:
 print('a == b')
else:
 print('a < b')
s = input()
n = len(s)
x, y = map(int, input().split())
dx = []
dy = []
xy = 0
cnt =0
for i in s:
    if i == 'F':
        cnt += 1
    else:
        xy += 1
        xy %= 2
        if xy:
            dx.append(cnt)
        else:
            dy.append(cnt)
        cnt = 0
if cnt != 0:
    if xy:
        dy.append(cnt)
    else:
        dx.append(cnt)
sum_x = sum(dx) + 2
sum_y = sum(dy) + 2
dpx = [[0] * sum_x for i in range(len(dx))]
dpy = [[0] * sum_y for i in range(len(dy))]

if dx:
    dpx[0][dx[0]] = True
if dy:
    dpy[0][dy[0]] = True
    dpy[0][-dy[0]] = True
for i in range(1, len(dx)):
    for j in range(0, sum_x):
        dpx[i][j] = dpx[i-1][j-dx[i]] or dpx[i-1][(j+dx[i])%sum_x]
for i in range(1, len(dy)):
    for j in range(0, sum_y):
        dpy[i][j] = dpy[i-1][j-dy[i]] or dpy[i-1][(j+dy[i])%sum_y]
print('Yes' if x < sum_x and dpx[-1][x] and y < sum_y and dpy[-1][y] else 'No')



### FIXED CODE ###

s = input() + 'T'
n = len(s)
x, y = map(int, input().split())
X = [[], [0]]
xy = 0
cnt =0
for i in s:
    if i == 'F':
        cnt += 1
    else:
        X[xy].append(cnt)
        xy = 1 - xy
        cnt = 0

def f(l):
    if len(l) == 0:
        return [0]
    post = [l[0]]
    for i in range(1, len(l)):
        if l[i]:
            pre = sorted(post)
            post = []
            for j in range(len(pre)):
                if j == 0 or pre[j] != pre[j-1]:
                    post.append(pre[j]+l[i])
                    post.append(pre[j]-l[i])
    return post

print('Yes' if x in f(X[0]) and y in f(X[1]) else 'No')
S = input()
T = input()

mS = []
d = len(S) - len(T)

for j in range(d):
    m = 0
    for i in range(len(T)):
        if S[i] == T[i] :
            m += 1

    mS.append(m)
    S = S[1:]
print(len(T) - max(mS))

### FIXED CODE ###

S = input()
T = input()

mS = []
d = len(S) - len(T)
m = 0

if len(S) == len(T) :
    for i in range(len(T)):
        if S[i] != T[i] :
            m += 1
    print(m)

else :

    for j in range(d):
        m = 0
        for i in range(len(T)):
            if S[i] != T[i] :
                m += 1

        mS.append(m)
        S = S[1:]
    print(min(mS))
while True:
    h, w = map( int, input().split() )
    if not h and not w: break
    print('#' * w +'\n' + ('#' + '.' * w-2 + '#\n') * h-2 + '#' * w + '\n')

### FIXED CODE ###

while True:
    h, w = map( int, input().split() )
    if not h and not w:
        break
    if h <3 or w < 3:
        print(("#" * w + "\n") * h)
    else:
        print('#' * w +'\n' + ('#' + '.' * (w-2) + '#\n') * (h-2) + '#' * w + '\n')
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, c = LI()
    if a <= c <= b:
        print("Yes")
        return
    print("No")
    return

#B
def B():
    n, m = LI()
    e = defaultdict(int)
    for i in range(1, n + 1): e[i] = 0
    for i in range(m):
        a, b = LI()
        e[a] += 1
        e[b] += 1
    for i in e.values():
        print(i)
    return

#C
def C():
    n, k = LI()
    d = [0] * (n+1)
    for i in range(n):
        a, b = LI()
        d[a] += b
    for i in range(n+1):
        k -= d[i]
        if k <= 0:
            print(i)
            return
    return

#D
def D():
    return

#Solve
if __name__ == '__main__':
    C()


### FIXED CODE ###

N, K = map(int, input().split())
A = [0 for _ in range(10 ** 5)]
for i in range(N):
    a, b = map(int, input().split())
    A[a - 1] += b
for i in range(10 ** 5):
    if K - A[i] > 0:
        K = K - A[i]
    else:
        print(i + 1)
        break
N, M = map(int, input().split())
A = list(map(int, input().split()))

j = 0
sum = []

for i in range(N+1):
    if i == A[j]:
        sum.append(0)
        if j < M-1:
            j += 1
            continue
    elif i == 0 or i == 1:
        sum.append(1)
    else:
        sum.append(sum[i-2] + sum[i-1])


print(sum[N]%1000000007)

### FIXED CODE ###

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

j = 0
sum = []

for i in range(N+1):
    if j < M and i == A[j]:
        sum.append(0)
        if j < M-1:
            j += 1
    elif i == 0 or i == 1:
        sum.append(1)
    else:
        sum.append(sum[i-2] + sum[i-1])


print(sum[N]%1000000007)
import math
import itertools

N,M,Q = map(int, input().split())
a = [0]*Q
b = [0]*Q
c = [0]*Q
d = [0]*Q
for i in range(Q):
    a[i],b[i],c[i],d[i] = map(int, input().split())

maximum = 0
lis = list(range(1, M+1, 1))
for pair in itertools.combinations(lis, N):
    sum = 0
    pair = list(pair)
    for i in range(N):
        if pair[b[i]-1]-pair[a[i]-1] == c[i]:
            sum += d[i]
            
    if maximum < sum:
        maximum = sum

print(maximum)


### FIXED CODE ###

from itertools import combinations_with_replacement as combr

N,M,Q = map(int, input().split())
a, b, c, d = [0]*Q, [0]*Q, [0]*Q, [0]*Q
for i in range(Q):
    a[i],b[i],c[i],d[i] = map(int, input().split())

ans = 0
# lis = list(range(1, M+1))
for pair in combr(range(1,M+1), N):
    tmp = 0
    pair = list(pair)
    for i in range(Q):
        if (pair[b[i]-1]-pair[a[i]-1]) == c[i]:
            tmp += d[i]
            
    ans=max(ans, tmp)

print(ans)
def distance(a,b,c,d):
    return ((c-a)**2+(d-b)**2)**(1/2)
def sankaku(a,b,c,d,e,f):
    S=1/2*abs((c-a)*(f-b)-(e-a)*(d-b))
    return (distance(a,b,c,d)*distance(c,d,e,f)*distance(e,f,a,b))/(4*S)
from itertools import combinations
n=int(input())
XY=[list(map(int,input().split()))for i in range(n)]
if n>=3:
    kumiawase=list(combinations(range(n),3))
    ans=0
    for tu in kumiawase:
        p,q = XY[tu[0]]
        r,s = XY[tu[1]]
        t,u = XY[tu[2]]
        ans=max(ans,sankaku(p,q,r,s,t,u))
    print(ans)
else:
    ans=distance(XY[0][0],XY[0][1],XY[1][0],XY[1][1])
    print(ans)

### FIXED CODE ###

n = int(input())
XY = []
for i in range(n):
    x, y = map(int, input().split())
    XY.append((x, y))


# 外積、平行判定
def cross(a, b):
    return a.real * b.imag - b.real * a.imag


# 内積、直行判定
def dot(a, b):
    return a.real * b.real + a.imag * b.imag


# 外心の中心
def circumcenter(a, b, c):
    bunshi = (a - b) * dot(c, c) + (b - c) * dot(a, a) + (c - a) * dot(b, b)
    bunbo = (a - b) * c.conjugate() + (b - c) * a.conjugate() + (c - a) * b.conjugate()
    if bunbo == 0:
        return False, 0
    return True, bunshi / bunbo


kouho = []
for i in range(n - 1):
    a, b = XY[i]
    z1 = complex(a, b)
    for j in range(i + 1, n):
        c, d = XY[j]
        z2 = complex(c, d)
        kouho.append((z1 + z2) / 2)
if n >= 3:
    for i in range(n - 2):
        a, b = XY[i]
        z1 = complex(a, b)
        for j in range(i + 1, n - 1):
            c, d = XY[j]
            z2 = complex(c, d)
            for k in range(j + 1, n):
                e, f = XY[k]
                z3 = complex(e, f)
                flag, gaishin = circumcenter(z1, z2, z3)
                if flag:
                    kouho.append(gaishin)
ans = 10 ** 10
for z in kouho:
    temp = 0
    for i in range(n):
        x, y = XY[i]
        z1 = complex(x, y)
        temp = max(temp, abs(z - z1))
    ans = min(ans, temp)
print(ans)
# python3
# -*- coding: utf-8 -*-
import sys
import math
from math import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint

INF = float('inf')

ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
sys.setrecursionlimit(1000000000)


def lcm(a, b):
    return (a * b) // gcd(a, b)


# main
S, T = input().split()
A, B = mis()
U = input()

if U == S:
    print(str(A-1) + " " + str(B))
else:
    print(str(A) + " " + str(B-1))


### FIXED CODE ###

# python3
# -*- coding: utf-8 -*-
import sys
import math
#from math import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint

INF = float('inf')

ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
sys.setrecursionlimit(1000000000)


def lcm(a, b):
    return (a * b) // gcd(a, b)


# main
S, T = input().split()
A, B = mis()
U = input()

if U == S:
    print(str(A-1) + " " + str(B))
else:
    print(str(A) + " " + str(B-1))
S = input()
K = int(input())
N = len(S)
cnt = 0
flg1 = False
flg2 = False
flg3 = False
flg4 = False
flg5 = False
for i in range(N-1):
    if S[i] != S[i+1]:
        flg3 = True
        break
if (flg3 == False) and N % 2 == 1:
    print((N*K)//2)
    exit()


if (S[0] == S[N-1]) and K != 1:
    if S[0] != S[1]:
        cnt += 1
        flg1 = True
        flg5 = True
    if (S[1] == S[2]) and (2 < N) and (flg5 == False):
        cnt += 1
        flg1 = True
if (S[N-2] == S[N-1]):
    flg4 = True

for i in range(N-1):
    if flg2:
        flg2 = False
        continue
    if (i == N - 2) and flg1:
        break
    if S[i] == S[i+1]:
        cnt += 1
        flg2 = True
if flg1 and flg4 == False:
    print(cnt*K-1)
else:
    print(cnt*K)

### FIXED CODE ###

def f(s,n):
    res = 0
    flg = False
    for i in range(1,n):
        if flg:
            flg = False
            continue
        if S[i] == S[i-1]:
            flg = True
            res += 1
    return res
S = input()
K = int(input())
if len(set(list(S))) == 1:
    print(len(S)*K//2)
    exit()
ans = f(S,len(S))
S = S * 2
print(ans + (f(S,len(S)) - ans) * (K-1))
def christmasEve():
    N, K = map(int, input().split())
    h = [int(input()) for i in range(N)]
    strees = sorted(h)
    result=10**9
    for i in range(len(strees)):
        result = min(result, strees[i+K-1] - strees[i])
    print(result)

if __name__ == "__main__":
    christmasEve()

### FIXED CODE ###

def christmasEve():
    N, K = map(int, input().split())
    h = [int(input()) for i in range(N)]
    strees = sorted(h)
    result=10**9
    for i in range(N-K+1):
        result = min(result, strees[i+K-1] - strees[i])
    print(result)

if __name__ == "__main__":
    christmasEve()
h,w,a,b=map(int,input().split())m=10**9+7;f=[1]
for i in range(h+w):f+=[f[-1]*(i+1)%m]
def comb(a,b,m):return f[a]*pow(f[b],m-2,m)*pow(f[a-b],m-2,m)%m
x=0
for i in range(b,w):x+=comb(h-a+i-1,i,m)*comb(a+w-i-2,a-1,m)%m
print(x%m)

### FIXED CODE ###

h,w,a,b=map(int,input().split());m=10**9+7;f=[1]
for i in range(h+w):f+=[f[-1]*(i+1)%m]
def comb(a,b,m):return f[a]*pow(f[b],m-2,m)*pow(f[a-b],m-2,m)%m
x=0
for i in range(b,w):x+=comb(h-a+i-1,i,m)*comb(a+w-i-2,a-1,m)%m
print(x%m)
(n, x) = map(int, input().split())
l = list(map(int, input().split()))

count = 0
for i in range(n - 2):
    if count > x:
        ans = i
        break
    else:
        count += l[i]
print(ans)

### FIXED CODE ###

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

d = 0
ans = 0
for i in l:
    if d > x:
        break
    else:
        d += i
        ans += 1

if x >= sum(l):
    ans += 1

print(ans)
import sys
sys.setrecursionlimit(4100000)

def find(Data, x):
    if Data[x] < 0:
        return x
    else:
        Data[x] = find(Data, x)
        return Data[x] 

def unite(Data, a, b):
    a, b = find(Data, a), find(Data, b)
    if a != b:
        if Data[a] < Data[b]:
            Data[a] = Data[a] + Data[b]
            Data[b] = a
        else:
            Data[b] = Data[b] + Data[a]
            Data[a] = b 

n, m = map(int, input().split())
UF = [-1 for i in range(n)]
for i in range(m):
    ai, bi = map(int, input().split())
    ai, bi = ai - 1, bi - 1
    unite(UF, ai, bi)

ans = 0
for i in range(n):
    if UF[i] < 0: ans += 1 
print(ans - 1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def find(Data, x):
    if Data[x] < 0:
        return x
    else:
        Data[x] = find(Data, Data[x])
        return Data[x] 

def unite(Data, a, b):
    a, b = find(Data, a), find(Data, b)
    if a == b:
        pass
    elif Data[a] < Data[b]:
        Data[a] = Data[a] + Data[b]
        Data[b] = a
    else:
        Data[b] = Data[b] + Data[a]
        Data[a] = b 

n, m = map(int, input().split())
UF = [-1 for i in range(n)]
for i in range(m):
    ai, bi = map(int, input().split())
    ai, bi = ai - 1, bi - 1
    unite(UF, ai, bi)

ans = 0
for i in range(n):
    if UF[i] < 0: ans += 1 
print(ans - 1)
_=input()
A=map(lambda x:("A", int(x)), input())
B=map(lambda x:("B", int(x)), input())
C=map(lambda x:("C", int(x)), input())
S = sorted(A, cmp=lambda x, y:-x[1] + y[1])

A=None
B=None
C=None
for i in len(S):
  if A==None and x[0]=="A":
    A=i
  elif B==None and x[0]=="B":
    B=i
  elif C==None and x[0]=="C":
  	C=i

for i in [A, B, C].sort()[::-1]:
  del S[i]

print(S)


### FIXED CODE ###

N,Q=map(int,input().split())
S=input()

lis = [0] * len(S)
for i in range(len(S)):

  if i>0:
    lis[i] += lis[i-1]
  if i < len(S)-1 and S[i] == 'A' and S[i+1] == 'C':
    lis[i+1] += 1


for _ in range(Q):
  L = tuple(map(int, input().split()))

  c = 0
  print(lis[L[1]-1]-lis[L[0]-1])
N = int(input())
A = [int(i) for i in input().split(' ')]
for i in range(10**9):
 if sum([i%2 for i in A])>0:
  print(i)
  break
 else: A = [i/2 for i in A]

### FIXED CODE ###

import numpy
S = input()
print(numpy.array([i=='1' for i in S]).sum())