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

def main():
    import sys
    input = sys.stdin.readline
    N, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    XY.sort()
    XY = tuple(XY)

    def count(x_min, x_max, y_min, y_max, i, j):
        OK = 0
        NG = 0
        a = j - i + 1 - K
        for m in range(i, j + 1):
            if y_min <= XY[m][1] <= y_max:
                OK += 1
            else:
                NG += 1
            if OK >= K:
                return True
            if NG > a:
                return False

    ans = 10 ** 20
    for i in range(N - 1):
        a = XY[i][0]
        for j in range(i + K - 1, N):
            b = XY[j][0]
            for k in range(N):
                c = XY[k][1]
                for l in range(N):
                    d = XY[l][1]
                    if c < d:
                        if count(a, b, c, d, i, j):
                            # print ('A')
                            ans = min(ans, (b - a) * (d - c))
    print (ans)
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

#PythonだとTLEする
N, K = map(int, input().split())
X = [0] * N
Y = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    X[i] = x
    Y[i] = y

def count(x_min, x_max, y_min, y_max):
    cnt = 0
    for i in range(N):
        if x_min <= X[i] <= x_max and y_min <= Y[i] <= y_max:
            cnt += 1
    return cnt

ans = 10 ** 20
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                # print ('i, j , k, l = ', i, j, k, l)
                if X[i] < X[j] and Y[k] < Y[l]:
                    if count(X[i], X[j], Y[k], Y[l]) >= K:
                        # print ('A')
                        ans = min(ans, (X[j] - X[i]) * (Y[l] - Y[k]))
print (ans)
### BUGGY CODE ###

def add2(l):
    ys = []
    for i in range(len(l)):
        ys += [l[i] + x for x in l[i+1:]]
    return ys


def add(n, l):
    if not l:
        return []
    elif n == 1:
        return l
    elif n == 2:
        return add2(l)
    else:
        ys = add(n, l[1:])
        ys += [l[0] + x for x in add(n-1, l[1:])]
        return ys


def main():
    n, a = (int(x) for x in input().split())
    xs = [int(x) for x in input().split()]
    tot = sum(xs)

    if n == 1:
        count = len([x for x in xs if x == a])
    else:
        count = 0
        lop = n // 2 + 1
        for i in range(1, n//2+1):
            ys = add(i, xs)
            count += len([y for y in ys if y == a * i])
            if n - i > i:
                zs = [tot - x for x in ys]
                count += len([z for z in zs if z == a * (n - i)])
        if sum(xs) == n * a:
            count += 1

    print(count)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np
n,avea=tuple(map(lambda x:int(x),input().split()))
x=list(map(lambda x:int(x), input().split()))
x=np.array(x)
x=x-avea
w=max(abs(min(x)),abs(max(x)))*n
dp=np.zeros((n+1,2*w+1),dtype=int)
dp[0,w]=1
for i in range(n):
    for j in range(2*w+1):
        if 0<=j-x[i]<=2*w:
            dp[i+1,j]=dp[i,j]+dp[i,j-x[i]]
        else:
            dp[i+1,j]=dp[i,j]
print(dp[n,w]-1)
### BUGGY CODE ###

import numpy as np

n, d, a  = map(int,input().split())
x = []
h = []
for i in range(n):
    x_temp,h_temp = map(int,input().split())
    x.append(x_temp)
    h.append(h_temp)

x = np.array(x, dtype=np.int64)
h = np.array(h, dtype=np.int64)
sort_ind = np.argsort(x)
x = x[sort_ind]
h = h[sort_ind]

ans = 0
for i in range(n):
    if (h[i] <= 0):
        continue
    at_num = ((h[i] -1 )// a) + 1
    ans += at_num
    h[i] -= at_num * a
    x_origin = x[i]
    while(True):
        i += 1
        if(i >= n):
            break
        if(x_origin + 2*d >= x[i]):
            h[i] -= at_num * a
        else:
            break

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
# 二分木
import bisect


n,d,a = map(int,input().split())
xh = [list(map(int, input().split())) for _ in range(n)]

xh.sort()
x = [ tmp[0] for tmp in xh]
damage = [0] * (n+1)

ans = 0
for i in range(n):
    damage[i+1] += damage[i]
    if( damage[i+1] >= xh[i][1] ):
        continue
    atk_num = (xh[i][1] - damage[i+1] - 1)//a +1
    ans += atk_num
    damage[i+1] += atk_num * a
    right = bisect.bisect_right(x, xh[i][0] + 2*d)
    if( right < n):
        damage[right+1] -= atk_num * a

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

# -*- coding: utf-8 -*-

n = int(input())
nums = list(map(int, input().split()))
x = 10 ** 9 + 7

ans = 0

for i in range(1, n):
    ans += (sum(nums[:i]) % x) * nums[i]
    ans = ans % x

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

n = int(input())
nums = list(map(int, input().split()))
x = 10 ** 9 + 7

ans = 0

sums = [0] * (n - 1)

for j in range(n - 1):
    if j == 0:
        sums[0] = nums[0] % x
    else:
        sums[j] = (sums[j - 1] + nums[j]) % x

for i in range(1, len(nums)):
    ans += sums[i - 1] * nums[i]
    ans = ans % x

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

def bisect_left(A, x):
    l, r = -1, len(A)
    while r - l > 1:
        m = (l + r) // 2
        if A[m] >= x:
            r = m
        else:
            l = m
    return r


def bisect_right(A, x):
    l, r = -1, len(A)
    while r - l > 1:
        m = (l + r) // 2
        if A[m] > x:
            r = m
        else:
            l = m
    return r


def count_pair(A, x):
    # A内のペアで積がxより小さいものの個数
    N = len(A)
    cnt = 0
    for n in range(N - 1):
        if A[n] < 0:
            y = x // A[n]
            # n+1番以降でyより大きいものの個数
            cnt += N-max(n+1, bisect_right(A, y))
        elif A[n] > 0:
            y = -(-x // A[n])
            # n+1番以降でyより小さいものの個数
            cnt += max(n+1, bisect_left(A, y)) - (n + 1)
        else:  # A[n]==0
            if x > 0:
                cnt += N - n - 1
    return cnt


# A = [0, 0, 0, 1, 1, 2, 2, 2]
# print(bisect_left(A, 0))
# print(bisect_left(A, 1))
# print(bisect_left(A, 2))
# print(bisect_right(A, 0))
# print(bisect_right(A, 1))
# print(bisect_right(A, 2))
# exit()

# count_pair(x)<Kをみたすxの最大値を求める
N, K = map(int, input().split())
* A, = map(int, input().split())
A.sort()
inf = 10**18+1
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(A, c) < K:
        l = c
    else:
        r = c
print(l)


### FIXED CODE ###

import numpy as np


def count_pair(x):
    # A内のペアで積がxより小さいものの個数
    # まず(i,j)と(j,i)を重複して数える
    cnt = 0
    # A[i]<0なる各iに対してA[j]>x/A[i]なるjの個数
    cnt += (N-np.searchsorted(A, x//A_nega, side='right')).sum()
    if x > 0:
        # 各iに対してA[j]=0なるjの個数
        cnt += len(A_zero)*N
    # A[i]>0なる各iに対してA[j]<x/A[i]なるjの個数
    cnt += np.searchsorted(A, -(-x//A_posi), side='left').sum()
    # i=jを除いてから2で割る
    cnt = (cnt-(A**2 < x).sum())//2
    return cnt


# count_pair(x)<Kをみたすxの最大値を二分探索で求める
N, K = map(int, input().split())
* A, = map(int, input().split())
A = np.array(A)
A = np.sort(A)
A_posi = A[A > 0]
A_zero = A[A == 0]
A_nega = A[A < 0]
inf = 10**18+1
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(c) < K:
        l = c
    else:
        r = c
print(l)
### BUGGY CODE ###

S = input()
T = input()
ans = True
for i in range(len(S)):
    li =  []
    for j in range(len(S)):
        if S[j] == S[i]:
            li.append(j)
    for j in li:
        if T[li[0]] != T[j]:
            ans = False

for i in range(len(T)):
    li =  []
    for j in range(len(T)):
        if T[j] == T[i]:
            li.append(j)
    for j in li:
        if S[li[0]] != S[j]:
            ans = False
if ans:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

Sp = list(input())
Tp = list(input())
S = [ord(Sp[i])-ord('a') for i in range(len(Sp))]
T = [ord(Tp[i])-ord('a') for i in range(len(Tp))]
lis = [-1]*26
lit = [-1]*26
ans = True
for i in range(len(S)):
    if lis[S[i]] == -1:
        lis[S[i]] = T[i]
    else:
        if lis[S[i]] != T[i]:
            ans = False
            break
for i in range(len(T)):    
    if lit[T[i]] == -1:
        lit[T[i]] = S[i]
    else:
        if lit[T[i]] != S[i]:
            ans = False
            break
if ans:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

def main():
  s=list(input())
  q=int(input())
  ok=1
  for i in range(q):
    query=list(input().split())
    if query[0]=='1':
      ok=(ok+1)%2
    else:
      f,c=query[1],query[2]
      if ok:
        if f=='1':
          s=[c]+s
        else:
          s+=[c]
      else:
        if f=='1':
          s=s+[c]
        else:
          s=[c]+s
  if ok:
    print(''.join(s))
  else:
    print(''.join(s[::-1]))
if __name__=='__main__':
  main()


### FIXED CODE ###

from collections import deque
def main():
  s=deque(list(input()))
  q=int(input())
  ok=1
  for i in range(q):
    query=list(input().split())
    if query[0]=='1':
      ok=(ok+1)%2
    else:
      f,c=query[1],query[2]
      if ok:
        if f=='1':
          s.appendleft(c)
        else:
          s.append(c)
      else:
        if f=='1':
          s.append(c)
        else:
          s.appendleft(c)
  s=list(s)
  if ok:
    print(''.join(s))
  else:
    print(''.join(s[::-1]))
if __name__=='__main__':
  main()
### BUGGY CODE ###

import numpy as np
n, w = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(n)]
items = np.array(items)
# dp[n-1][w] solution
# dp[i][w] = max(dp[i-1][w-items[0][0]]+items[0][1], dp[i-1][w])
dp = np.zeros((n,w+1), dtype='int64')
if items[0][0] <= w:
    dp[0, items[0][0]:] = items[0][1]
for i in range(1,n):
    for j in range(0,w+1):
        if j-items[i][0] >= 0:
            dp[i][j] = max(dp[i-1][j-items[i][0]]+items[i][1], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[n-1][w])


### FIXED CODE ###

import numpy as np
n, W = map(int, input().split())
dp = np.zeros((n,W+1), dtype='int64')
for i in range(n):
    w, v = map(int , input().split())
    dp[i, :w] = dp[i-1, :w]
    dp[i, w:] = np.fmax(dp[i-1, w:], dp[i-1,:W-w+1]+v)
print(dp[n-1][W])
### BUGGY CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))

dp = np.ones(max(A)+1, dtype=bool)

for a in A:
    ind = [a * i for i in range(2, max(A)//a + 1)]
    dp[ind] = False
dub = [x for x in set(A) if A.count(x) > 1]
dp[dub] = False
print(sum(dp[A]))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
MAX = max(A)
dp = [True for _ in range(MAX+1)]

for a in set(A):
    for k in range(2*a,MAX+1,a):
        dp[k] = False
B = sorted(A)
for i in range(len(B)-1):
    if B[i] == B[i+1]:
        dp[B[i]] = False

print(sum(dp[a] for a in set(A)))
### BUGGY CODE ###

#coding:utf-8
#1_11_C 2015.4.20
class Dice:
    def __init__(self,ary):
        self.top , self.south , self.east , self.west , self.north ,self.bottom = ary

    def roll_n(self):
        self.top , self.south , self.bottom , self.north = self.south , self.bottom , self.north , self.top

    def roll_e(self):
        self.top , self.west , self.bottom , self.east = self.west , self.bottom , self.east , self.top

    def twist(self):
        self.north , self.west , self.south , self.east = self.east , self.north , self.west , self.south

dice1 = Dice(input().split())
dice2 = Dice(input().split())

while dice1.top != dice2.top or dice1.south != dice2.south:
    if dice1.top == dice2.top:
        while dice1.south != dice2.south:
            dice1.twist()
    elif dice1.south == dice2.south:
        while dice1.top != dice2.top:
            dice1.roll_e()
    else:
        dice1.roll_n()

if dice1.top == dice2.top and dice1.north == dice2.north and dice1.south == dice2.south and dice1.east == dice2.east and dice1.west == dice2.west and dice1.bottom == dice2.bottom:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

#coding:utf-8
#1_11_C

class Dice:
    def __init__(self, ary):
        self.top, self.south, self.east, self.west, self.north, self.bottom = ary

    def roll_n(self):
        self.top, self.north, self.bottom, self.south = self.south, self.top, self.north, self.bottom

    def roll_e(self):
        self.top, self.east, self.bottom, self.west = self.west, self.top, self.east, self.bottom

    def twist(self):
        self.north, self.east, self.south, self.west = self.west, self.north, self.east, self.south

    def isEqual(self, dice):
        if self.top == dice.top and self.south == dice.south and self.east == dice.east and self.west == dice.west and self.north == dice.north and self.bottom == dice.bottom:
            return True
        else:
            return False

dice1 = Dice(map(int,input().split()))
dice2 = Dice(map(int,input().split()))

flag = False

for i in range(6):
    if i % 2 == 0:
        dice1.roll_n()
    else:
        dice1.roll_e()

    for j in range(4):
        if dice1.isEqual(dice2):
            flag = True
            break
        else:
            dice1.twist()

    if flag:
        break

if flag:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
l = []
r = []
for i in range(Q):
    l_i, r_i = map(int, input().split())
    l.append(l_i)
    r.append(r_i)

ac_flag = [0] * len(S)

for i in range(len(S)-1):
    if S[i: i + 2] == 'AC':
        ac_flag[i] = 1

for i in range(Q):
    print(sum(ac_flag[l[i]-1:r[i]-1]))


### FIXED CODE ###

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

c = [0] * N

for i in range(N-1):
    if S[i:i+2] == 'AC':
        c[i+1] = c[i] + 1
    else:
        c[i+1] = c[i]

for _ in range(Q):
    l, r = map(int, input().split())
    print(c[r-1] - c[l-1])
### BUGGY CODE ###

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

for i in range(m//n, 0, -1):
    if m % i != 0:
        continue
    print(i)
    break


### FIXED CODE ###

n, m = map(int, input().split())
 
for i in range(m//n, 0, -1):
    if m % i != 0:
        continue
    print(i)
    break
### BUGGY CODE ###

import numpy as np
import re

def main():
    S = input()
    N = len(S) + 1

    ans = 0
    s_list = re.split("(><)", S)
    nelem = len(s_list)
    for i in range(nelem):
        elem = s_list[i]
        if elem == "><":
            pass
        else:
            ln = elem.count(">") + 1
            rn = elem.count("<") + 1
            if i == 0:
                rn -= 1
            if i == nelem - 1:
                ln -= 1
            nmax = np.max([ln, rn])
            nmin = np.min([ln, rn])
            #print("===")
            #print([rn, ln])
            #print(np.arange(start=0, stop=nmax+1, step=1))
            #print(np.arange(start=0, stop=nmin-1, step=1))
            ans += np.sum(np.arange(start=0, stop=nmax+1, step=1))
            ans += np.sum(np.arange(start=0, stop=nmin, step=1))
    #print(s_list)
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import re
 
def main():
    S = input()
    N = len(S) + 1
 
    ans = 0
    s_list = re.split("><", S)
    nelem = len(s_list)
    for i in range(nelem):
        elem = s_list[i]
        ln = elem.count(">") + 1
        rn = elem.count("<") + 1
        if i == 0:
            rn -= 1
        if i == nelem - 1:
            ln -= 1
        nmax = max([ln, rn])
        nmin = min([ln, rn])
        ans += (0 + nmax) * (nmax + 1) / 2
        ans += (0 + nmin - 1) * (nmin) / 2
    print(int(ans))
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def main():
  s = input()
  n = len(s)
  mod = 10**9+7
  dp = [[0]*13 for _ in range(n+1)]
  dp[0][0] = 1
  d = {(j, k):(10*j+k)%13 for k in range(10) for j in range(13)}
  for i in range(n):
    if s[i] != "?":
      t = int(s[i])
      for j in range(13):
        dp[i+1][(10*j+t)%13] += dp[i][j]
        dp[i+1][(10*j+t)%13] %= mod
    else:
      for k in range(10):
        for j in range(13):
          dp[i+1][(10*j+k)%13] += dp[i][j]
          dp[i+1][(10*j+k)%13] %= mod
  print(dp[n][5]%mod)
if __name__ == "__main__":
  main()

### FIXED CODE ###

s = input()
n = len(s)
mod = 10**9+7
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
d = {(j, k):(10*j+k)%13 for k in range(10) for j in range(13)}
for i in range(n):
  if s[i] != "?":
    t = int(s[i])
    for j in range(13):
      dp[i+1][d[(j, t)]] += dp[i][j]
      dp[i+1][d[(j, t)]] %= mod
  else:
    for k in range(10):
      for j in range(13):
        dp[i+1][d[(j, k)]] += dp[i][j]
        dp[i+1][d[(j, k)]] %= mod
print(dp[n][5]%mod)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = str(input())
i = []
j = 1
while j <= (N + 1):
    part_S = S[0:j]
    i = i + [part_S.count('AC')]
    j += 1
k = 1
#print (i)
while k <= Q:
    l, r = map(int, input().split())
    ans = i[r-1]-i[l-1]
    k += 1
    print (ans)

### FIXED CODE ###

N, Q = map(int, input().split())
S = str(input())
i = [0] * (N + 1)
j = 1
while j < N:
    i[j+1] = i[j] 
    if (S[j-1] == 'A' and S[j] == 'C'):
        i[j+1] += 1
    j += 1
k = 0
#print (i)
while k < Q:
    l, r = map(int, input().split())
    ans = i[r]-i[l]
    k += 1
    print (ans)
### BUGGY CODE ###

from networkx import*
def main():
    g=Graph()
    for a in[*open(x:=0)][1:]:
        a,b=map(int,a.split())
        g.add_edge(a,b+.5)
    for c in connected_components(g):
        s=g.subgraph(c)
        a,b=map(len,bipartite.sets(s))
        x+=a*b-s.size()
    print(x)
main()

### FIXED CODE ###

class UnionFind():
    def __init__(self,size):
        self.table=[-1]*size
    def root(self,x):
        while self.table[x]>=0:
            x=self.table[x]
        return x
    def unite(self,x,y):
        s1=self.root(x)
        s2=self.root(y)
        if s1!=s2:
            if self.table[s1]>self.table[s2]:
                s1,s2=s2,s1
            self.table[s1]+=self.table[s2]
            self.table[s2]=s1
        return
    def same(self,x,y):
        return self.root(x)==self.root(y)
    def size(self,x):
        return -self.table[self.root(x)]
n,*z=map(int,open(0).read().split())
u=UnionFind(10**5*2+1)
for x,y in zip(*[iter(z)]*2):
    u.unite(x,10**5+y)
d=[[0,set(),set()]for _ in range(10**5*2+1)]
for x,y in zip(*[iter(z)]*2):
    t=d[u.root(x)]
    t[0]+=1
    t[1].add(x)
    t[2].add(y)
print(sum(len(x)*len(y)-a for a,x,y in d))
### BUGGY CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
mod = 10**9+7

N = int(input())
al = [[] for i in range(N+1)]

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

    al[a].append(b)
    al[b].append(a)

b = [0 for i in range(N + 1)]
w = [0 for i in range(N + 1)]
seen = [0 for i in range(N + 1)]

def mul_list(a):
    ans = 1
    for aa in a:
        ans = (ans * aa) % mod
    return ans

@functools.lru_cache(None)
def bfs(u):
    seen[u] = 1
    tmp1 = []
    tmp2 = []

    flag = 0
    for w in al[u]:
        if seen[w] == 0:
            seen[w] = 1
            bb, ww = bfs(w)
            tmp1.append(ww)
            tmp2.append(bb + ww)
            flag = 1

    if flag == 0:
        return 1, 1

    ans_b = mul_list(tmp1)
    ans_w = mul_list(tmp2)

    return ans_b, ans_w

p, q = bfs(1)

print((p + q) % mod)






### FIXED CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
mod = 10**9+7

N = int(input())
al = [[] for i in range(N+1)]

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

    al[a].append(b)
    al[b].append(a)

b = [0 for i in range(N + 1)]
w = [0 for i in range(N + 1)]
seen = [0 for i in range(N + 1)]

@functools.lru_cache(None)
def bfs(u):
    seen[u] = 1

    b[u] = 1
    w[u] = 1

    for v in al[u]:
        if seen[v] == 0:
            seen[v] = 1
            bfs(v)
            b[u] = (b[u] * w[v]) % mod
            w[u] = (w[u] * ((b[v] + w[v]) % mod)) % mod

bfs(1)

print((b[1] + w[1]) % mod)
### BUGGY CODE ###

import heapq

def mk_idx(y,x):
    return y*32+x

H,W=map(int, input().split())
DINF = 100000
S = []
S.append('#' * (W+2))
for i in range(H):
    S.append('#'+ input() + '#')
S.append('#' * (W+2))
dmax = 0
G = [ [] for _ in range( mk_idx(22,22) ) ]
for y in range(1,H+1):
    for x in range(1,W+1):
        if (S[y][x] == '.'):
            idx = mk_idx(y,x)
            if (S[y-1][x] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y-1,x) )
            if (S[y][x-1] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y,x-1) )
            if (S[y+1][x] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y+1,x) )
            if (S[y][x+1] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y,x+1) )

for y in range(1,H+1):
    for x in range(1,W+1):
        if S[y][x] == '.':
            d = [ DINF for _ in range( mk_idx(22,22) ) ]
            q = []
            heapq.heappush(q, [0, mk_idx(y,x)])
            while len(q) != 0:
                v = heapq.heappop(q)
                n = v[0]
                idx = v[1]
                d[ idx ] = n;
                dmax = max(dmax, n)
                for nv in G[ idx ]:
                    if d[ nv ] <= n+1 :
                        continue
                    heapq.heappush(q, [n+1, nv ] )
print(dmax)


### FIXED CODE ###

from collections import deque

def mk_idx(y,x):
    return y*22+x

H,W=map(int, input().split())
DINF = 100000
S = []
S.append('#' * (W+2))
for i in range(H):
    S.append('#'+ input() + '#')
S.append('#' * (W+2))
dmax = 0
G = [ [] for _ in range( mk_idx(22,22) ) ]
for y in range(1,H+1):
    for x in range(1,W+1):
        if (S[y][x] == '.'):
            if (S[y-1][x] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y-1,x) )
            if (S[y][x-1] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y,x-1) )
            if (S[y+1][x] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y+1,x) )
            if (S[y][x+1] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y,x+1) )

for y in range(1,H+1):
    for x in range(1,W+1):
        if S[y][x] == '.':
            d = [ DINF for _ in range( mk_idx(22,22) ) ]
            d[ mk_idx(y,x) ] = 0
            q = deque( [mk_idx(y,x)] )
            while len(q) != 0:
                v = q.popleft()
                n = d[v];
                dmax = max(dmax, n)
                for nv in G[v]:
                    if d[ nv ] <= n+1 :
                        continue
                    d[ nv ] = n+1
                    q.append(nv)
print(dmax)
### BUGGY CODE ###

import heapq as hq



def resolve():
    (N,T)=(int(i) for i in input().split())

    dishes=[[int(i) for i in input().split()] for _ in range(N)]
    dishes.sort()
    dpt=[[-1 for i in range(T+1)] for _ in range(N+1)]
    vflg=[[False for i in range(T+1)] for _ in range(N+1)]
    dpt[0][0]=0
    q=[]
    hq.heappush(q,(0,0))

    while q:
        
        (ind,cost)=hq.heappop(q)

        if vflg[ind][cost]:
            continue
        vflg[ind][cost]=True
        if ind==N:
            break


        aft=min(cost+dishes[ind][0],T)
        sc=dpt[ind][cost]
        if dpt[ind+1][cost]<sc:
            dpt[ind+1][cost]=sc
            hq.heappush(q,(ind+1,cost))
        if cost==T:
            continue
        if dpt[ind+1][aft]<sc+dishes[ind][1]:
            dpt[ind+1][aft]=sc+dishes[ind][1]
            hq.heappush(q,(ind+1,aft))



    print(max(dpt[-1]))


if __name__ == "__main__":

    resolve()

### FIXED CODE ###


def resolve():
    (N,T)=(int(i) for i in input().split())

    dishes=[[int(i) for i in input().split()] for _ in range(N)]
    dishes.sort()
    dpt=[[-1 for i in range(T+1)] for _ in range(N+1)]

    dpt[0][0]=0

    for i in range(N):
        for j in range(T):
            dpt[i+1][j]=max(dpt[i+1][j],dpt[i][j])
            dpt[i+1][min(T,j+dishes[i][0])]=max(dpt[i+1][min(T,j+dishes[i][0])],dpt[i][j]+dishes[i][1])
        dpt[i+1][T]=max(dpt[i+1][T],dpt[i][T])




    print(max(dpt[-1]))
#    for i in dpt:
#        print(i)

if __name__ == "__main__":
#    unittest.main()
    resolve()