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

h, w, k = map(int, input().split())
S = [[int(s) for s in list(input())] for i in range(h)]
ans = 10**4
for b in range(2**(h-1)):
    cnt = bin(b).count('1')
    B = format(b, 'b').zfill(h-1)+'1'
    T = [[0]*w for i in range(cnt+1)]
    for j in range(w):
        t, c = 0, 0
        for i in range(h):
            t += S[i][j]
            if B[i] == '1':
                T[c][j] += t
                t = 0
                c += 1
    if max([max(T[i]) for i in range(cnt+1)]) > k:
        continue
    A = [T[i][0] for i in range(cnt+1)]
    tmp = cnt
    for j in range(1, w):
        A = [A[i]+T[i][j] for i in range(cnt+1)]
        if any([a > k for a in A]):
            A = [T[i][j] for i in range(cnt+1)]
            tmp += 1
    ans = min(ans, tmp)
print(ans)


### FIXED CODE ###

# 部分リストのリスト
def all_sublist(lst):
    lstlst = []
    for i in range(2**len(lst)):
        sublst = []
        for j in range(len(lst)):
            if (i >> j) & 1 == 1:
                sublst.append(lst[j])
        lstlst.append(sublst)
    return lstlst


# 入力
H, W, K = map(int, input().split())
S = [[int(x) for x in list(input())] for h in range(H)]

# 横方向にカットする位置の列挙
cutlst = all_sublist(list(range(1, H)))

# 横方向の切り方を動かして切る数の合計の最小値を求める
cnt_min = 10**9 + 7
for cut in cutlst:
    # 横方向に切って圧縮したものをSSとする
    SS = []
    cut.append(H)
    start = 0
    for stop in cut:
        T = []
        for w in range(W):
            tmp = 0
            for h in range(start, stop):
                tmp += S[h][w]
            T.append(tmp)
        SS.append(T)
        start = stop
    H0 = len(SS)
    # K以上の成分があったらこのcutはパス
    if any([SS[h][w] > K for h in range(H0) for w in range(W)]):
        continue
    # 縦方向に切る数を数える
    cnt = len(cut) - 1
    left = [0 for h in range(H0)]
    right = [SS[h][0] for h in range(H0)]
    for w in range(1, W):
        left, right = right, [right[h] + SS[h][w] for h in range(H0)]
        leftOK = all([left[h] <= K for h in range(H0)])
        rightNG = any([right[h] > K for h in range(H0)])
        # すべての成分がK以下になるギリギリのところで切る
        if leftOK and rightNG:
            left = [0 for h in range(H0)]
            right = [SS[h][w] for h in range(H0)]
            cnt += 1
    cnt_min = min(cnt_min, cnt)
print(cnt_min)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200005)
n, q = map(int, input().split())

to = [[] for i in range(n+1)]


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

score = [0]*(n+1)
for i in range(q):
    p, x = map(int, input().split())
    score[p] += x


def down_tree(index, parent):
    for i in to[index]:
        if i == parent:
            continue
        score[i] += score[index]
        down_tree(i, index)



down_tree(1, 1)

print(' '.join(map(str, score[1:])))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(200005)
n, q = map(int, input().split())

to = [[] for i in range(n+1)]


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

score = [0]*(n+1)
for i in range(q):
    p, x = map(int, input().split())
    score[p] += x


def down_tree(index, parent):
    for i in to[index]:
        if i == parent:
            continue
        score[i] += score[index]
        down_tree(i, index)



down_tree(1, 1)

print(' '.join(map(str, score[1:])))
### BUGGY CODE ###

#coding: UTF-8

x=int(input('>'))

i=1

while x !=0:
    print('Case {}: {}'.format(i,x))
    i=i+1



### FIXED CODE ###

c = 0

while True:
    x = int(input())
    c +=1
    
    if x == 0:
        break
   
    print("Case {}: {}".format(c, x))
### BUGGY CODE ###

P,C = map(int,input().split())
pref = [[] for _ in range(P)]
city = []
for ci in range(C):
  p,y = map(int,input().split())
  city.append(p-1)
  pref[p-1].append([y,ci])
cinp = []
for pi in range(P):
  pref[pi].sort()
  cnow = ['null' for _ in range(C)]
  for j in range(len(pref[pi])):
    citycode = pref[pi][j][1]
    cnow[citycode] = j
  cinp.append(cnow)
for ci in range(C):
  pnow = city[ci]
  inow = cinp[pnow][ci]
  try:
    ans = (pnow+1) * 10 ** 6 + (inow+1)
  except:
    print(pnow,inow,p,cinp)
  ANS = str(ans)
  print( '0' * (12 - len(ANS)) + ANS)

### FIXED CODE ###

P,C = map(int,input().split())
pref = [[] for _ in range(P)]
city = []
for ci in range(C):
  p,y = map(int,input().split())
  city.append([p-1])
  pref[p-1].append([y,ci])
cinp = []
for pi in range(P):
  pref[pi].sort()
  for j in range(len(pref[pi])):
    citycode = pref[pi][j][1]
    city[citycode].append(j)
for ci in range(C):
  pnow = city[ci][0]
  inow = city[ci][1]
  try:
    ans = (pnow+1) * 10 ** 6 + (inow+1)
  except:
    print(pnow,inow,p,cinp)
  ANS = str(ans)
  print( '0' * (12 - len(ANS)) + ANS)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    A = tuple(map(int, input().split()))
    import fractions
    from functools import reduce

    def lcm_base(x, y):
        return (x * y) // fractions.gcd(x, y)

    def lcm(*numbers):
        return reduce(lcm_base, numbers, 1)

    ans = 0
    LCM = lcm(*A)
    for i in range(N):
        ans += LCM//A[i]

    print(ans%(10**9+7))
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import fractions
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
g = 1
MOD = 10**9+7
ans = 0

for i in A:
    tmp = g*i//fractions.gcd(g, i) # それまでのLCM
    ans *= tmp//g
    g = tmp
    ans += g//i

print(ans%MOD)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
m = max(a)
count = 0
nishin = []

while True:
    m, r = divmod(m, 2)
    count += 1
    if m == 0:
        break

for i in range(0, N):
    for j in range(0, count):
        a[i], r = divmod(a[i], 2)
        nishin.append(str(r))
    a[i] = ''.join(reversed(nishin))
    nishin.clear()

for k in range(0, N):
    q = ''
    for j in range(0, count):
        p = 0
        for i in range(0, N):
            if i == k:
                pass
            else:
                p += int(a[i][j])
        p %= 2
        q += str(p)
    nishin.append(q)

jusshin = [int(i, 2) for i in nishin]

ans = ''

for i in range(0, N-1):
    ans += (str(jusshin[i]) + ' ')

ans += str(jusshin[N-1])
print(ans)


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
x = 0
for i in range(0, N):
    x ^= a[i]
ans = []
for i in range(0, N):
    ans.append(str(x ^ a[i]))

print(' '.join(ans))
### BUGGY CODE ###

n = int(raw_input())
num_list = []
for i in xrange(n):
  num_list.append(int(raw_input()))
#print num_list

max = 1 - pow(10, 9)

for i in range(n - 1):
  for j in range(i + 1, n):
    tmp = num_list[j] - num_list[i]
#    print "i = %d, j = %d, tmp = %d" % (i, j, tmp)
    if tmp > max:
      max = tmp

print max

### FIXED CODE ###

n = int(raw_input())
num_list = [int(raw_input()) for i in xrange(n)]

minv = num_list[0]
maxv = -1000000000

for i in xrange(1, n):
  tmp = num_list[i] - minv
  maxv = tmp if tmp > maxv else maxv
  minv = num_list[i] if minv > num_list[i] else minv
  # print "i = %d, tmp = %d, maxv = %d, minv = %d" % (i, tmp, maxv, minv)

print maxv
### BUGGY CODE ###

from decimal import Decimal
from numba import njit, i4, i8


@njit(i8(i8, i4), cache=True)
def div(n, d):
    cnt = 0
    while n % d == 0:
        n //= d
        cnt += 1
    return cnt


n = int(input())
arr = [int(Decimal(input()) * 10**9) for _ in range(n)]
arr = [(div(x, 2), div(x, 5)) for x in arr]

ans = 0
for i in range(len(arr)):
    for j in range(i + 1, len(arr)):
        (a, b), (c, d) = arr[i], arr[j]
        if a + c >= 18 and b + d >= 18:
            ans += 1

print(ans)

### FIXED CODE ###

def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
dp = [[0]*19 for _ in range(19)]

ans = 0
for _ in range(n):
    x = round(float(input()) * pow(10, 9))
    two = div(x, 2)
    five = div(x, 5)
    ans += dp[18 - two][18 - five]
    for i in range(two + 1):
        for j in range(five + 1):
            dp[i][j] += 1

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

n = int(input())
s = input()

r = s.count("R")
g = s.count("G")
b = s.count("B")


ans = r * g * b

for i in range(n):
    for j in range(i + 1, n):
        if 2 * j - i > n - 1:
            continue
        if s[i] == s[j] or s[i] == s[2 * j - i] or s[j] == s[2 * j - i]:
            pass
        else:
            ans -= 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

r = s.count("R")
g = s.count("G")
b = s.count("B")


ans = r * g * b

for i in range(n):
    for j in range(i + 1, n):
        if 2 * j - i > n - 1:
            continue
        if s[i] == s[j] or s[i] == s[2 * j - i] or s[j] == s[2 * j - i]:
            pass
        else:
            ans -= 1
print(ans)
### BUGGY CODE ###

h, w = map(int, input().split())
t = [input() for _ in range(h)]
U = [[0] * (w + 2) for _ in range(h + 2)]
D = [[0] * (w + 2) for _ in range(h + 2)]
L = [[0] * (w + 2) for _ in range(h + 2)]
R = [[0] * (w + 2) for _ in range(h + 2)]
ans = 0
for i in range(1, 1 + h):
    for j in range(1, 1 + w):
        if t[i - 1][j - 1] == "#":
            U[i][j] = 0
            L[i][j] = 0
        else:
            U[i][j] = U[i - 1][j] + 1
            L[i][j] = L[i][j - 1] + 1
for i in range(h, 0, -1):
    for j in range(w, 0, -1):
        if t[i - 1][j - 1] == "#":
            D[i][j] = 0
            R[i][j] = 0
        else:
            D[i][j] = D[i + 1][j] + 1
            R[i][j] = R[i][j + 1] + 1
        tmp = U[i][j] + D[i][j] + L[i][j] + R[i][j]
        if tmp > ans:
            ans = tmp
print(ans - 3)


### FIXED CODE ###

def f(h, w):
    t = [input() for _ in range(h)]
    U = [[0] * (w + 2) for _ in range(h + 2)]
    D = [[0] * (w + 2) for _ in range(h + 2)]
    L = [[0] * (w + 2) for _ in range(h + 2)]
    R = [[0] * (w + 2) for _ in range(h + 2)]
    ans = 0
    Ui1 = U[0]
    for i in range(1, 1 + h):
        Ui = U[i]
        Li = L[i]
        ti1 = t[i - 1]
        for j, tk in enumerate(ti1):
            j += 1
            if tk == "#":
                Ui[j] = 0
                Li[j] = 0
            else:
                Ui[j] = Ui1[j] + 1
                Li[j] = Li[j - 1] + 1
        Ui1 = Ui
        Di1 = D[-1]
    for i in range(h, 0, -1):
        Ui = U[i]
        Li = L[i]
        Di = D[i]
        Ri = R[i]
        ti1 = t[i - 1]
        for j in range(w, 0, -1):
            if ti1[j - 1] == "#":
                Di[j] = 0
                Ri[j] = 0
            else:
                Di[j] = Di1[j] + 1
                Ri[j] = Ri[j + 1] + 1
                tmp = Ui[j] + Di[j] + Li[j] + Ri[j]
                if tmp > ans:
                    ans = tmp
        Di1 = Di
    print(ans - 3)

h, w = map(int, input().split())
f(h, w)
### BUGGY CODE ###

R=range
M=998244353
n,m,k=map(int,input().split())
f=1
for i in R(n):f*=i+1
r=[pow(f,M-2,M)]
for i in R(n):r+=r[i]*(n-i)%M,
print(sum(f//n*m*r[i-n]*r[~i]*pow(m-1,~i+n,M)for i in R(k+1))%M)

### FIXED CODE ###

M=998244353
class Factorial:
    def __init__(self,n):
        self.f=f=[0]*(n+1)
        f[0]=b=1
        for i in range(1,n+1):f[i]=b=b*i%M
        self.inv=inv=[0]*(n+1)
        inv[n]=b=pow(self.f[n],-1,M)
        for i in range(n,0,-1):inv[i-1]=b=b*i%M
    def factorial(self,i):
        return self.f[i]
    def ifactorial(self,i):
        return self.inv[i]
    def comb(self,n,k):
        if n>=k:return self.f[n]*self.inv[n-k]*self.inv[k]%M
        else:return 0
comb=Factorial(10**5*5).comb
n,m,k=map(int,input().split())
print(sum(m*comb(n-1,i)*pow(m-1,~i+n,M)for i in range(k+1))%M)
### BUGGY CODE ###

import numpy as np

n,m = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(m)]
n = np.array([0]*n)
for l,r in LR:
  n[l-1:r] += 1.
print(sum(n == m))

### FIXED CODE ###

n,m = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(m)]
L = max([i[0] for i in LR])
R = min([i[1] for i in LR])
print(max(R-L+1,0))
### BUGGY CODE ###

""" C
    https://atcoder.jp/contests/aising2020/tasks/aising2020_c
"""
import sys
import math
from functools import reduce
from bisect import bisect_left

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return reduce(lambda acc, _: acc + [readIntegerSet(m)], range(0, n), [])

def main(N):
    for n in range(1, N+1):
        count = 0
        maxi = int(math.sqrt(N))
        x = 1
        for x in range(1, maxi):
            for y in range(1, maxi):
                # z^2 + (x + y) * z = n - pow(x, 2) - pow(y, 2) - x * y
                # z^2 + 2 * z = 3
                a = n - pow(x, 2) - pow(y, 2) - x * y
                z = 0
                for z in range(1, maxi):
                    if pow(z, 2) + (x+y)*z == a:
                        count += 1
                    z += 1
                y += 1
            x += 1
        print(count)

if __name__ == "__main__":
    _N = readInteger()

    main(_N)

### FIXED CODE ###

""" C
    https://atcoder.jp/contests/aising2020/tasks/aising2020_c
"""
import sys
import math
from functools import reduce
from bisect import bisect_left

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return reduce(lambda acc, _: acc + [readIntegerSet(m)], range(0, n), [])

def main(N):
    maxi = int(math.sqrt(N))
    result = dict()
    for x in range(1, maxi+1):
        for y in range(1, maxi+1):
            for z in range(1, maxi+1):
                n = pow(x, 2) + pow(y, 2) + pow(z, 2) + x*y + y*z + z*x
                if n not in result.keys():
                    result[n] = 1
                else:
                    result[n] += 1

    for n in range(1, N+1):
        if n in result.keys():
            print(result[n])
        else:
            print(0)

if __name__ == "__main__":
    _N = readInteger()

    main(_N)
### BUGGY CODE ###

n = int(input())

print(0, flush=True)
s = input()
if s == 'Vacant':
    exit()
head_v = s
head_i = 0
print(n-1, flush=True)
s = input()
if s == 'Vacant':
    exit()
tail_v = s
tail_i = n-1

while True:
    mi = (head_i + tail_i) // 2
    print(mi, flush=True)
    s = input()
    if s == 'Vacant':
        exit()
    if s == head_v ^ (mi-head_i-1) % 2 == 1:
        head_i = mi
        head_v = s
    else:
        tail_i = mi
        tail_v = s


### FIXED CODE ###

n = int(input())

print(0, flush=True)
s = input()
if s == 'Vacant':
    exit()
head_v = s
head_i = 0
print(n-1, flush=True)
s = input()
if s == 'Vacant':
    exit()
tail_v = s
tail_i = n-1

while True:
    mi = (head_i + tail_i) // 2
    print(mi, flush=True)
    mv = input()

    if mv == 'Vacant':
        exit()
    if tail_v == mv and (tail_i - mi) % 2 == 1 or tail_v != mv and (tail_i - mi) % 2 == 0:
        head_i = mi
        head_v = mv
    else:
        tail_i = mi
        tail_v = mv
### BUGGY CODE ###

import collections as col
from collections import defaultdict as dd

d=dd(list)

N,M=map(int, input().split())
p=[-1]*N
p[0]=1

for _ in range(M):
    i,j=map(int, input().split())
    if i>j:
        i,j=j,i
    d[i].append(j)

for i in d:
    for j in d[i]:
        if p[i-1]==-1:
            if p[j-1]==-1:
                if i<j:
                    p[i-1]=i
                    p[j-1]=i
                else:
                    p[i-1]=j
                    p[j-1]=j
            else:
                p[i-1]=p[j-1]
        else:
            if p[j-1]==-1:
                p[j-1]=p[i-1]
            else:
                if p[i-1]<p[j-1]:
                    p[i-1]=p[j-1]
                else:
                    p[j-1]=p[i-1]

for i,a in enumerate(p):
    if i!=a-1 and a>=0 and p.count(i+1)>1:
        p=[i if k==a else k for k in p]

ans=col.Counter(p)

if ans.most_common()[0][0]==-1:
    print(ans.most_common()[1][1])
else:
    print(ans.most_common()[0][1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:
        return
    
    if rank[a]<rank[b]:
        par[a]=b
        rank[b]+=rank[a]
        rank[a]=rank[b]
    else:
        par[b]=a
        rank[a]+=rank[b]
        rank[b]=rank[a]

    return

def chk(a,b):
    if par[a]==par[b]:
        print('Yes')
    else:
        print('No')

    return

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

par=(list(range(N+1)))
rank=[1]*(N+1)

for _ in range(M):
    A,B=map(int, input().split())
    union(A,B)

print(max(rank))
### BUGGY CODE ###

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

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

a = sorted( a )
print(sum(a[-N:]))

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1])
for b,c in bc[::-1]:
  a.extend([c]*b)
  if len(a)>2*n:
    break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

from collections import deque
def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].add(v)
        else:
            d[u]={v}
    s,t=map(int,input().split())
    ans=chk=0
    w=deque([0,s])
    tmp=[0]*(n+1)
    n*=3
    ans=1
    while n:
        x=w.pop()
        if x==0:
            n-=1
            ans+=1
            w.appendleft(0)
        elif x in d:
            for j in d[x]:
                if tmp[j]==0 or tmp[j]%3!=ans%3:
                    w.appendleft(j)
                    tmp[j]=ans
        if ans%3==0 and tmp[t]==ans:
            print(ans//3)
            exit()
    print(-1)

if __name__=="__main__":
    sol()


### FIXED CODE ###

from collections import deque
def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    w=deque([0,s])
    #tmp=[0]*(n+1)
    tmp=[[0,0,0] for i in range(n+1)]
    ans=1
    n+=n//2
    n*=2
    while n:
        x=w.pop()
        if x==0:
            ans+=1
            n-=1
            w.appendleft(0)
        elif x in d:
            for j in d[x]:
                if ans%3==0 and j==t:
                    print(ans//3)
                    exit()
                if tmp[j][ans%3]==0:
                    w.appendleft(j)
                    tmp[j][ans%3]=1
    print(-1)

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

a,b, k=map(int, input().split())
for i in range(k):
    if a>=1:
        a-=1
    elif b>=1:
        b-=1

print(str(a)+" "+str(b))

### FIXED CODE ###

a,b, k=map(int, input().split())
if k>=a+b:
    print("0 0")
elif k>a:
    print("0"+" "+str(b-(k-a)))
else:
    print(str(a-k)+" "+str(b))
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))


for i in range(N):
    B = list(A)
    B.pop(i)
    print(max(B))

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))

max_A = max(A)
next_A = sorted(A, reverse=True)[1]
for i in range(N):
    if A[i] != max_A:
        print(max_A)
    else:
        print(next_A)
### BUGGY CODE ###

X = int(input())

A = 0
while(True):
    if(pow(A, 5) >= X):
        break
    else:
        A += 1

Aminus1 = A-1
Apow5 = pow(A,5)
Aminus1pow5 = pow(A-1, 5)

B = 0
while(True):
    Bpow5 = pow(B, 5)
    if(Apow5-Bpow5 == X):
        print(A, B)
        break
    elif(Aminus1pow5 + Bpow5 == X):
        print(A-1, -B)
        break
    else:
        B +=1


### FIXED CODE ###

X = int(input())

for A in range(-118, 120):
    for B in range(-119, 119):
        A5 = pow(A,5)
        B5 = pow(B,5)
        if( (A5-B5) == X):
            ans = str(A) + ' ' + str(B)
            break

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

# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2104
TLE
"""
import sys
from sys import stdin
input = stdin.readline


def main(args):
    t = int(input())
    for _ in range(t):
        n, k = map(int, input().split())
        houses = [int(x) for x in input().split()]

        if k >= n:              #  ????????¨?????????????????¨?????§??????
            print(0)
            continue

        diff = []
        prev = houses[0]
        for h in houses[1:]:
            temp = h - prev
            diff.append(temp)
            prev = h



        points = []
        s_diff = sorted(diff)
        for x in range(k-1):
            pos = diff.index(s_diff.pop())
            points.append(pos)
            diff[pos] = -1


        cable_total = 0
        prev = 0
        for p in points:
            cable_total += houses[p] - houses[prev]
            prev = p + 1
        if prev != (n - 1):
            cable_total += houses[-1] - houses[prev]

        print(cable_total)


if __name__ == '__main__':
    main(sys.argv[1:])

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2104
AC
"""
import sys
from sys import stdin
input = stdin.readline


def main(args):
    t = int(input())
    for _ in range(t):
        n, k = map(int, input().split())
        houses = [int(x) for x in input().split()]

        if k >= n:              #  ????????¨?????????????????¨?????§????????´???
            print(0)
            continue

        # ??¶??????????????¢????¨????????????????????????¨????????????????????????
        gaps = []
        prev = houses[0]
        for i, h in enumerate(houses[1:]):
            gaps.append((h - prev, i))
            prev = h

        # gap?????§????????¨??????????????????????????????????????´????????????
        gaps.sort(reverse=True)
        gaps = gaps[:k-1]


        # ???????????????????????±????????????????¨??????????
        cable_total = 0
        prev = 0
        for _, p in gaps:
            cable_total += houses[p] - houses[prev]
            prev = p + 1
        if prev != (n - 1):
            cable_total += houses[-1] - houses[prev]

        print(cable_total)


if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

n,max_w = map(int,input().split())
w=[]
v=[]

for i in range(n):
  tmp_w,tmp_v = map(int,input().split()) 
  w.append(tmp_w)
  v.append(tmp_v)
  
dp=[[0]*(max_w+1) for i in range(n)]

#dp[i番目の品まで入れられる][重さがj以下]
for j in range(max_w+1):
  if j < w[0]:
    dp[0][j]=0
  else:
    dp[0][j]=v[0]
    
for i in range(0,n-1):
  for j in range(max_w+1):
    if j < w[i+1]:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j],dp[i][j-w[i+1]]+v[i+1])
print(dp[n-1][max_w])

### FIXED CODE ###

n,w = map(int,input().split())
info = [[0,0]]+[list(map(int,input().split())) for i in range(n)]

## dp[i][j]:i番目までのアイテムを重さjのナップサックに詰めるときの最大価値
dp = [[0]*(w+1) for i in range(n+1)]
for i in range(n+1):
  for j in range(w+1):
    if j-info[i][0]>=0:
      dp[i][j] = max(dp[i-1][j],dp[i-1][j-info[i][0]]+info[i][1])
    else:
      dp[i][j] = dp[i-1][j]

print(dp[n][w])