Harryxun/stf_run huggingface dataset:
N,K=map(int,input().split())
a=list(map(int,input().split()))
index=a.index(1)
l=index
r=index
cnt=0
if index<=(N//2-1 if N%2==0 else N//2):
  while l!=0:
    if cnt==0:
      if l-K+1<0:
        r=K-1
    l=max(0,l-K+1)
    cnt+=1
  while r!=N-1:
    r=min(N-1,r+K-1)
    cnt+=1
  print(cnt)
else:
  while r!=N-1:
    if cnt==0:
      if r+K-1>N-1:
        l=N-K
    r=min(N-1,r+K-1)
    cnt+=1
  while l!=0:
    l=max(0,l-K+1)
    cnt+=1
  print(cnt)

### FIXED CODE ###

N,K=map(int,input().split())
if (N-1)%(K-1)==0:
  print((N-1)//(K-1))
else:
  print((N-1)//(K-1)+1)
s = input()
if (s = "AAA" or s = "BBB"):
  print("No")
else:
  print("Yes")

### FIXED CODE ###

s = input()
if (s == "AAA" or s == "BBB"):
  print("No")
else:
  print("Yes")
from functools import reduce


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

numerator = reduce(lambda a, b: a * b, A)
denominator = 0
for i in range(n):
    denominator += reduce(lambda a, b: a * b, A[:i] + A[i+1:])
print(1.0 * numerator / denominator)


### FIXED CODE ###

from functools import reduce


n = int(input())
A = list(map(int, input().split()))
if n == 1:
    print(A[0])
else:
    numerator = reduce(lambda a, b: a * b, A)
    denominator = 0
    for i in range(n):
        denominator += reduce(lambda a, b: a * b, A[:i] + A[i+1:])
    print(1.0 * numerator / denominator)
r = int(input())
print("{0:f} {1:f}".format(r**2 * 3.14, 2 * r * 3.14))



### FIXED CODE ###

import math
r = float(input())  #入力値が実数の時
print("{0} {1}".format(r**2 * math.pi, 2 * r * math.pi))
n = int(input())
a,b = input().split()
a = [i for i in a]
b = [i for i in b]
ans =""

for i in range(n):
  ans += a[n]
  ans += b[n]
print(ans)


### FIXED CODE ###

n = int(input())
a,b = input().split()
a = list(a)
b = list(b)
ans =""
 
for i in range(n):
  ans += a[i]
  ans += b[i]
print(ans)
# coding: utf-8
import numpy as np
N, A, B = map(int, input().split())
print("N:", N, "A:", A, "B:", B)
if A == 0:
    print(0)
elif B == 0:
    print(N)
elif N <= A:
    print(N)
elif N <= A + B:
    print(A)
else:
    lst = np.array([1 for i in range(A)])
    # print(lst)
    lst2 = np.array([0 for i in range(B)])
    # print(lst2)
    lst3 = np.append(lst, lst2)
    # print(lst3)
    while lst3.size < N:
        lst3 = np.append(lst3, lst3)
    lst3 = lst3[:N]
    print(np.count_nonzero(lst3 == 1))

### FIXED CODE ###

# coding: utf-8
N, A, B = map(int, input().split())
# print("N:", N, "A:", A, "B:", B) 
if A == 0:
    print(0)
elif B == 0 or N <= A:
    print(N)
else:
    num = int(N / (A + B)) * A + min(A, N % (A + B))
    print(num)
s = input()

print("Yes" if s[3]==s[4] and s[5]==s[6] else "No")

### FIXED CODE ###

s = input()

print("Yes" if s[2] == s[3] and s[4] == s[5] else "No")
def main():
  n = int(input())
  i = int(sqrt(n)) + 1
  while i * i > n: i -= 1
  while i >= 1:
    if n % i == 0
      print(i+n//i)
      return
    i -= 1
main()


### FIXED CODE ###

def main():
  n = int(input())
  i = int((n)**0.5) + 1
  while i * i > n: i -= 1
  while i >= 1:
    if n % i == 0:
      print(i+n//i-2)
      return
    i -= 1
main()
A,B,C,D,E,F=map(int,input().split())
M=[]
S=[]
for i in range(F//100*A+1):
    for j in range(F//100*B+1):
        t=i*100*A+j*100*B
        if t<=F and t!=0:
            M.append(t)
for i in range(F//C+1):
    for j in range(F//D+1):
        ta=i*C+j*D
        if ta<=F:
            S.append(ta)
tmp=0
for x in M:
    for y in S:
        f=x+y
        e=(100*y)/f
        if f<=F and e<=E:
            if e>tmp:
                tmp=e
                ans1,ans2=f,y
print(ans1,ans2)

### FIXED CODE ###

a,b,c,d,e,f=map(int,input().split())
a=100*a
b=100*b
dp1=[0]*(f+1)
dp2=[0]*(f+1)
for i in range(f+1):
    if i%a==0:
        if i+a<=f:
            dp1[i+a]=1
for i in range(f+1):
    if i==0 or dp1[i]==1:
        if i+b<=f:
            dp1[i+b]=1
for i in range(f+1):
    if i%c==0:
        if i+c<=f:
            dp2[i+c]=1
for i in range(f+1):
    if i==0 or dp2[i]==1:
        if i+d<=f:
            dp2[i+d]=1

ans=[-1,-1,-1]
for i in range(f+1):
    if dp1[i]==1:
        x=min(f-i,(i//100)*e)
        k=-1
        for j in range(x,-1,-1):
            if dp2[j]==1 or j==0:
                k=j
                if ans[0]<100*k/(i+k):
                    ans=[100*k/(i+k),i+k,k]
                break
print(str(ans[1])+" "+str(ans[2]))
def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    c = [0] + [abs(h[1] - h[0])]
    for i in range(2, n):
        min_step = 10 ** 4
        num = i if i <= k else k
        for j in range(num):
            step = abs(h[i] - h[i-j]) + c[i-j]
            if step < min_step:
                min_step = step
        c.append(min_step)
    print(c.pop())


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [0] + [float("inf")] * (n-1)
    for i in range(1, n):
        for j in range(max(0, i-k), i):
            dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]))
    
    print(dp[-1])


if __name__ == "__main__":
    main()
n = int(input().split())

num1 =  ( int(n[0]) * 3 + int(n[1]) ) // 2

print(num1)

### FIXED CODE ###

n =input().split()

num1 =  ( int(n[0]) * 3 + int(n[1])) // 2

print(num1)
T,X=map(int,inputs.split())
print(T/X)

### FIXED CODE ###

T,X=map(int,input().split())
print(format(T/X,'0.4f'))
a = input()
print (3*a*a)


### FIXED CODE ###

a = input()
print (3*int(a)*int(a))
import collections
import sys
sys.setrecursionlimit(100000000)

from math import factorial
def ncr(n,r):
 if n>2:
  return factorial(n) / factorial(r) / factorial(n - r)
 else:
  return 1
def solve():
  n = int(input())
  query = []
  for i in range(n):
    a = sorted(input())
    query.append("".join(a))

  c = collections.Counter(query)
  ans = 0
  tmp = c.values()

  for i in tmp:
    if i >=2:
      ans += ncr(i,2)
  print(int(ans))
  
solve()
  
  

### FIXED CODE ###

import collections
import sys
sys.setrecursionlimit(100000000)

from math import factorial
def ncr(n,r):
 if n==r:
  return 1
 elif n>2:
  return factorial(n) // factorial(r) // factorial(n - r)
 else:
  return 1
def solve():
  n = int(input())
  query = []
  for i in range(n):
    a = sorted(input())
    query.append("".join(a))

  c = collections.Counter(query)
  ans = 0
  tmp = list(c.values())

  for i in tmp:
    if i >=2:
      ans += ncr(i,2)
  print(int(ans))
solve()
ko,x=map(int,input().split())
s=max(x-ko+1,-1000000)
while True:
  print(s,end=" ")
  s+=1
  if s>min(ko+k-1,1000000):break


### FIXED CODE ###

k,x=map(int,input().split())
for i in range(k):
	print(x+i-k+1,end=" ")
if k != 1:
	print("",end="")
	for s in range(k)[1:]:
		print(x+s,end=" ")
import collections
N,K=map(int,input().split())
a=[]
K=K+1
while K>0:
  K=K-1
  d=int(input())
  a.append(map(str,input().split()))
e=collections.Counter(a)
print(N-len(a))

### FIXED CODE ###

import collections
N,K=map(int,input().split())
a=[]
d=[]
while K>0:
  K=K-1
  d.append(int(input()))
  b=list(map(int,input().split()))
  a.extend(b)
e=collections.Counter(a)
print(N-len(e))
#include <iostream>
#include <string>

using namespace std;

int main(){
  int a; 
  string s;
  cin >> a >> s;

  if (a < 3200) {
    cout << "red" << endl;
  } else {
    cout << s << endl;
  }
}

### FIXED CODE ###

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

if N >= 3200:
  print(S)
else:
  print("red")
import sys
sys.setrecursionlimit(100000000000000000)

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

def a(N, K):
    if abs(K - N) < K / 2:
        print(abs(K - N))
    else:
        a(abs(K - N), K)
        

if k == 1:
    print(0)
elif n < k / 2:
    print(n)
else:
    a(abs(k - n), k)
    


### FIXED CODE ###

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

if k > n:
    tmp = n
else:
    tmp = n % k

if tmp > k / 2:
    tmp = k - tmp

print(tmp)
# coding: utf-8
# 自分の得意な言語で
# Let's チャレンジ！！
if __name__ == '__main__':
    S = input()
    flg = True
    for index in range(len(S) - 1):
        if S[index]+S[index+1] == 'AC':
            print 'Yes'
            flg = False
            break
    if flg:
        print 'No'


### FIXED CODE ###

# coding: utf-8
# 自分の得意な言語で
# Let's チャレンジ！！
if __name__ == '__main__':
    S = raw_input()
    flg = True
    for index in range(len(S) - 1):
        if S[index]+S[index+1] == 'AC':
            print 'Yes'
            flg = False
            break
    if flg:
        print 'No'
import sys
import math


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

if N == 1:
    print(A[0]-X)
    sys.exit()

A.append(X)
A = sorted(A)

anslis = [0]*N

for i in range(N):
    anslis[i] = A[i+1] - A[i]

g = anslis.pop(0)
for c in cost_li:
    g = math.gcd(g,c)

print(g)

### FIXED CODE ###

import sys
import math


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

A.append(X)
A = sorted(A)

anslis = [0]*N
for i in range(N):
    anslis[i] = A[i+1] - A[i]

g = anslis.pop(0)
for c in anslis:
    g = math.gcd(g,c)

print(g)
import fractions

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

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
  
k=1
for a in A:
  k=lcm(k,a)
if k%2==0:
  k/=2
  
else:
  k*=1.5
print(int(M//k//2+M//k%2))



### FIXED CODE ###

import fractions

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

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
  
def kn(h):
  l=0
  while h%2==0:
    h=h//2
    l+=1
  return l
  
k=1
flag=kn(A[0]//2)
for a in A:
  a//=2
  k=lcm(k,a)
  if flag != kn(a):
    print(0);exit()
  
print(int(M//k//2+M//k%2))
import math
from functools import reduce
import itertools
import numpy as np

def solve():
    n = int(input())
    num = list(range(1,10))
    bit = 0
    for i in num:
        for j in num:
            if i * j == n:
                print("Yes")
                bit = 1
                break
    i bit == 0:
        print("No")
    return 0

if __name__ == "__main__":
    solve()


### FIXED CODE ###

import math
from functools import reduce
import itertools
import numpy as np

def solve():
    n = int(input())
    num = list(range(1,10))
    bit = 0
    for i in num:
        for j in num:
            if i * j == n:
                print("Yes")
                bit = 1
                break
        if bit == 1:
            break
    if bit == 0:
        print("No")
    return 0

if __name__ == "__main__":
    solve()
N = int(input())

edges = [[] for _ in range(N)]

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

colors = [-1] * (N - 1)

def func(a, p_color=-1):
    color = 1
    for b, i in edges[a]:
        if color == p_color:
            color += 1
        colors[i] = color
        func(b, color)
        color += 1

func(0, -1)

print(max(colors))
for c in colors:
    print(c)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

N = int(input())

edges = [[] for _ in range(N)]

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

colors = [-1] * (N - 1)

def func(a, p_color=-1):
    color = 1
    for b, i in edges[a]:
        if color == p_color:
            color += 1
        colors[i] = color
        func(b, color)
        color += 1

func(0, -1)

print(max(colors))
for c in colors:
    print(c)
def resolve():
    S = str(input())
    K = int(input())
    idx = S.find('1')

    if idx == -1:
        print(S[0])
        return
    else:
        if idx <= K:
            print(S[idx+1])
        else:
            print(S[0])
    return

resolve()


### FIXED CODE ###

def resolve():
    S = str(input())
    K = int(input())

    if S[0] != '1':
        print(S[0])
        return
    else:
        for i in range(1, K):
            if S[i] != '1':
                print(S[i])
                return
            else:
                continue
        print('1')

    return

resolve()
#!/usr/bin/env python
# -*- coding: utf-8 -*-

if __name__ == "__main__":
    import math
    a,b,c = map(int, raw_input().split())

    h = b * math.sin(math.pi * C / 180.0)
    S = h * a / 2.0
    L = math.sqrt((a - b * math.cos(math.pi * C / 180))**2 + h**2) + a + b
    
    print "%f" % S
    print "%f" % L
    print "%f" % h

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

if __name__ == "__main__":
    import math
    a,b,c = map(int, raw_input().split())

    h = b * math.sin(math.pi * c / 180.0)
    S = h * a / 2.0
    L = math.sqrt((a - b * math.cos(math.pi * c / 180))**2 + h**2) + a + b
    
    print "%f" % S
    print "%f" % L
    print "%f" % h
# sn, tn, qn = map(int, input().split())

sa = []
ta = []
qa = []
for i in range(sn):
    sa.append(int(input()))
for i in range(tn):
    ta.append(int(input()))
for i in range(qn):
    qa.append(int(input()))


def find_nearest(q, al, s, e):
    if e - s < 2:
        d1 = abs(q - al[s])
        d2 = abs(q - al[e])
        if d1 < d2:
            return al[s]
        return al[e]
    idx = (e - s) // 2 + s
    if al[idx] == q:
        return al[idx]
    if al[idx] > q:
        return find_nearest(q, al, s, idx)
    return find_nearest(q, al, idx, e)

def find_range(q1, q2, al, s, e):
    if al[s] >= q1 and al[s] <= q2:
        return True
    if al[e] >= q1 and al[e] <= q2:
        return True
    if al[s] >= q2 or al[e] <= q1 or e - s < 2:
        return False
    idx = (e - s) // 2 + s
    if al[idx] < q1:
        return find_range(q1, q2, al, s, idx)
    return find_range(q1, q2, al, idx, e)

def move_cost(q, al, bl):
    mx = find_nearest(q, al, 0, len(al) - 1)
    min_x = min(mx, q)
    max_x = max(mx, q)
    if find_range(min_x, max_x, bl, 0, len(bl) - 1):
        return max_x - min_x

    mx2 = find_nearest(mx, bl, 0, len(bl) - 1)
    return (max_x - min_x) + abs(mx2 - mx)

for q in qa:
    a1 = move_cost(q, sa, ta)
    a2 = move_cost(q, ta, sa)
    print(min(a1, a2))


### FIXED CODE ###

import bisect
sn, tn, qn = map(int, input().split())

LARGE = -100000000
sa = []
ta = []
qa = []
for i in range(sn):
    sa.append(int(input()))
for i in range(tn):
    ta.append(int(input()))
for i in range(qn):
    qa.append(int(input()))

def find_nearest(q, al, s, e):
    idx = bisect.bisect_right(al, q)
    if idx == 0:
        return [al[0], al[0]]
    if idx == len(al):
        return [al[idx - 1], al[idx - 1]]
    return [al[idx - 1], al[idx]]

def move_cost(q, al, bl):
    a1, a2 = find_nearest(q, al, 0, len(al) - 1)
    b1, b2 = find_nearest(q, bl, 0, len(bl) - 1)

    def calc(x1, x2, x3):
        y1 = min(x1, x2)
        y2 = max(x1, x2)
        if x3 >= y1 and x3 <= y2:
            return abs(x1 - x2)
        return abs(x1 - x2) + abs(x2 - x3)
    return min(
        calc(q, a1, b1),
        calc(q, a1, b2),
        calc(q, a2, b1),
        calc(q, a2, b2),
        calc(q, b1, a1),
        calc(q, b1, a2),
        calc(q, b2, a1),
        calc(q, b2, a2),
    )

for q in qa:
    print(move_cost(q, sa, ta))
str = input()
list = list(str)
abc = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
i = 0
while abc[i] in str:
    i += 1

if i > 26:
    print(abc[i])
else:
    print("None")

### FIXED CODE ###

str = input()
abc = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','aa']
i = 0
while abc[i] in str:
    if i < 26:
        i += 1
    else:
        break

if i < 26:
    print(abc[i])

else:
    print("None")
import math
n , k = map(int, input().split())

mod = 10 ** 9 + 7
red_count = n - k 
for i in range(1, k+1):
    b_dif = math.factorial(k-1) / (math.factorial(i-1) * math.factorial(k-i))
    
    a_dif = math.factorial(red_count + 1)  /  (math.factorial(i) * math.factorial(red_count + 1 - i))

    print(int(a_dif * b_dif % mod))

### FIXED CODE ###


from scipy.misc import comb
n , k = map(int, input().split())

mod = 10 ** 9 + 7
red_count = n - k 
for i in range(1, k+1) :
    if red_count + 1 - i < 0 :
        print(0)
        
    else:

        print(comb(red_count+1, i , exact = True)*comb(k-1, i-1, exact=True) % mod)
import itertools

P1=[p*(p+1)*(p+2)/6 for p in range(1,181)]
P2=[p for p in P1 if p%2]

maxnum=1000000

A1=[999999 for x in range(maxnum+1)]
A2=[999999 for x in range(maxnum+1)]

for X in [[P1,A1],[P2,A2]]:
    P=X[0]
    A=X[1]
    tmp=P
    bk=0
    cnt=2
    for p in tmp:
        if p<maxnum:
            A[p]=1
            bk+=1
    while bk<maxnum:
        tmp2=[]
        for t in tmp:
            for p in P:
                if t+p > maxnum:    break
                if A[t+p]>cnt:
                    A[t+p]=cnt
                    bk+=1
                    tmp2.append(t+p)
        tmp=tmp2[:]
        cnt+=1
while(1):
    n=int(raw_input())
    if n==0: break
    print A1[n], A2[n]



### FIXED CODE ###

import itertools

P1=[p*(p+1)*(p+2)/6 for p in range(1,181)]
P2=[p for p in P1 if p%2]

maxnum=1000000

A1=[5 for x in range(maxnum+1)]
A2=[37 for x in range(maxnum+1)]

for X in [[P1,A1],[P2,A2]]:
    P=X[0]
    A=X[1]
    mx=A[0]
    tmp=P
    bk=0
    cnt=2
    for p in tmp:
        if p<maxnum:
            A[p]=1
            bk+=1
    while cnt<mx:
        tmp2=[]
        for t in tmp:
            for p in P:
                if t+p > maxnum:    break
                if A[t+p]>cnt:
                    A[t+p]=cnt
                    bk+=1
                    tmp2.append(t+p)
        tmp=tmp2[:]
        cnt+=1
while(1):
    n=int(raw_input())
    if n==0: break
    print A1[n], A2[n]
N,M=map(int,input().split())
Key=[0]*(N+1)
for i in range(M):
    L,R = map(int,input().split())
    Key[L-1] += 1
    Key[R] -= 1
for i in range(N):
    Key[i+1] += Key[i] # 累積和
print(Key)
print(Key.count(m))


### FIXED CODE ###

N,M=map(int,input().split())
Key=[0]*(N+1)
for i in range(M):
    L,R = map(int,input().split())
    Key[L-1] += 1
    Key[R] -= 1
for i in range(N):
    Key[i+1] += Key[i] # 累積和
print(Key.count(M))
n=int(input())
a=list(map(int,input().split()))
min_a=0
ans=0
for i,z in enumerate:
  if i==0:continue
  if min_a>=z:
    ans+=1
  min_a=min(min_a,z)
print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
m=a[0]
ans=1
for i,z in enumerate(a):
  if i==0:continue
  if z<=m:
    ans+=1
  m=min(m,z)
print(ans)
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

a,b,k=map(int,input().split())
l=[]
g=gcd(a,b)
q=g
i=1

if a==1 and b==1:
  print(1)
else:
  for i in range(1,int(g/2)+1):
   
    if q%i==0:
      if int(g/i)==i:
        l.append(i)
      else:
        l.append(int(g/i))
        l.append(i)
  l.sort()
  l=set(l)
  l=list(l)
  print(l[(-1)*k])


### FIXED CODE ###

def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

a,b,k=map(int,input().split())
l=[]
g=gcd(a,b)

if a==1 and b==1:
  print(1)
else:
  for i in range(1,g):
    if g%i==0:
      l.append(i)
  l.append(g)
  print(l[(-1)*k])
N, Y = map(int, input().split())

for x in range(N+1):
    for y in range(N+1):
        if 10000*x + 5000*y + 1000*(N-(x+y)) == Y and N-(x+y) >= 0:
            print(x, y, N-(x+y))
            exit()

print(-1,-1,-1)

### FIXED CODE ###

S = input()
S_2 = S.replace("2017","2018")
print(S_2)
# https://atcoder.jp/contests/abc153/tasks/abc153_f
# 座標圧縮、貪欲法、imos法


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


# まず、何回攻撃すればいいのかを計算する。これがとにかく必要だ(なくてもいいけど)。
#
# 素直な戦略として、左から倒せるギリギリの爆弾を投下して倒すのが最適
# だけどナイーブに実装すると、O(N^2)。だから体力を管理するのが重要。
# どこにどれだけダメージが蓄積したのかはimos法(デルタ関数をおいてから累積和)で管理できる。

from bisect import bisect_left
N, D, A = read_ints()
XH = read_tuple(N)
XH.sort()  # 座標でソート

n_atk = []  # 何回攻撃するのが必要か
X = []  # 座標アクセス用配列
for x, h in XH:
    n_atk.append((h - 1) // A + 1)
    X.append(x)

damege = [0] * (N + 10)  # ダメージ管理用、配列外アクセスがめんどくさいので長めに取る
ans = 0
# j = 0  # 次のxが、今のx+2d以下でもっとも大きなidx
for i, (x, n) in enumerate(zip(X, n_atk)):
    damege[i] += damege[i - 1]  # 積分して、現時点の蓄積回数を表示
    atk = max(0, n - damege[i])  # iには何回攻撃したか
    ans += atk
    # 攻撃下回数を記録
    damege[i] += atk
    # 効果が切れる点を予約 # 尺取ならO(1)で次に行けるけど二分探索でも間に合うか
    damege[bisect_left(X, x + 2 * D + 1, lo=x)] -= atk  # 効果切れを予約

print(ans)


### FIXED CODE ###

# https://atcoder.jp/contests/abc153/tasks/abc153_f
# 座標圧縮、貪欲法、imos法


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


# まず、何回攻撃すればいいのかを計算する。これがとにかく必要だ(なくてもいいけど)。
#
# 素直な戦略として、左から倒せるギリギリの爆弾を投下して倒すのが最適
# だけどナイーブに実装すると、O(N^2)。だから体力を管理するのが重要。
# どこにどれだけダメージが蓄積したのかはimos法(デルタ関数をおいてから累積和)で管理できる。

from bisect import bisect_left
N, D, A = read_ints()
XH = read_tuple(N)
XH.sort()  # 座標でソート

n_atk = []  # 何回攻撃するのが必要か
X = []  # 座標アクセス用配列
for x, h in XH:
    n_atk.append((h - 1) // A + 1)
    X.append(x)

damege = [0] * (N + 10)  # ダメージ管理用、配列外アクセスがめんどくさいので長めに取る
ans = 0
# j = 0  # 次のxが、今のx+2d以下でもっとも大きなidx
for i, (x, n) in enumerate(zip(X, n_atk)):
    damege[i] += damege[i - 1]  # 積分して、現時点の蓄積回数を表示
    atk = max(0, n - damege[i])  # iには何回攻撃したか
    ans += atk
    # 攻撃下回数を記録
    damege[i] += atk
    # 効果が切れる点を予約 # 尺取ならO(1)で次に行けるけど二分探索でも間に合うか
    damege[bisect_left(X, x + 2 * D + 1, lo=i)] -= atk  # 効果切れを予約

print(ans)
n = int(input())
A = list(map(int,input().split()))
f = 1 
c = 0
while f == 1:
    f = 0
    for j in range(n-1,0,-1):
        if A[j] < A[j-1]:
        inc = A[j]
        A[j] = A[j-1] 
        A[j-1] = inc
        f = 1
        c += 1
print(" ".join(map(str,A)))
print(c)

### FIXED CODE ###

def bubblesort(a):
    count = 0
    swap = True
    while swap:
        swap = False
        for j in range(1,len(a))[::-1]:
            if a[j] < a[j-1]:
                ret = a[j]
                a[j] = a[j-1]
                a[j-1] = ret
                count += 1
                swap = True           
    print(" ".join(map(str,a)))
    print(count)
    
n = int(input())
a = list(map(int,input().split()))
bubblesort(a)
input()
A = [i for i in input().split()]
A.reverse()
print(' '.join(A))

### FIXED CODE ###

input()
A = [i for i in input().split()]
A.reverse()
print(' '.join(A))
def rec(c, a, x, n, m, start, states, best, price):

    for i in range(start, n):
        price += c[i]
        states[0] += a[i][0]
        states[1] += a[i][1]
        states[2] += a[i][2]

        if states[0] >= x and states[1] >= x and states[2] >= x and price < best:
            best = price

        if i != n - 1:
            best = rec(c, a, x, n, m, i + 1, states, best, price)

        states[0] -= a[i][0]
        states[1] -= a[i][1]
        states[2] -= a[i][2]
        price -= c[i]

    return best


def task(n, m, x, c, a):
    suma = [0] * n
    for i in range(0, n):
        for j in range(0, m):
            suma[j] += a[i][j]

    for j in range(0, m):
        if suma[j] < x:
            print(-1)
            return

    best = rec(c, a, x, n, m, 0, [0, 0, 0], 1000000, 0)

    print(best)


n, m, x = map(int, input().split())
c = []
a = []
for i in range(0, n):
    values = list(map(int, input().split()))
    c.append(values[0])
    a.append(values[1:])

task(n, m, x, c, a)


### FIXED CODE ###

def task(n, m, x, c, a):
    mx = [0] * m
    for i in range(0, n):
        for j in range(0, m):
            mx[j] += a[i][j]

    for j in range(0, m):
        if mx[j] < x:
            print(-1)
            return

    states = [0] * m

    best = 100000000
    for i in range(1, 2**n):
        price = 0

        for k in range(0, m):
            states[k] = 0

        for j in range(0, n):
            if ((i >> j) & 1):
                price += c[j]
                for k in range(0, m):
                    states[k] += a[j][k]

        if price < best:
            found = True
            for k in range(0, m):
                if states[k] < x:
                    found = False
                    break

            if found:
                best = price

    print(best)


n, m, x = map(int, input().split())
c = []
a = []
for i in range(0, n):
    values = list(map(int, input().split()))
    c.append(values[0])
    a.append(values[1:])

task(n, m, x, c, a)