CodeEff/ECCO huggingface dataset:
# Original solution
n,m,k=list(map(int,input().split()))
mod=10**9+7
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, list(range(n, n - r, -1)))
    under = reduce(mul, list(range(1,r + 1)))
    return over // under%mod
A=n*m
v=cmb(A-2,k-2)
t=0
y=0
for i in range(1,n):
  t+=i*(n-i)*m*m%mod
for i in range(1,m):
  y+=i*(m-i)*n*n%mod

ans=v*(t+y)
print((ans%mod))


# Optimized solution
n,m,k=list(map(int,input().split()))
mod=10**9+7
A=n*m-2
from math import factorial
def Comb(N, K):
    a = factorial(N) % mod
    b = factorial(K) % mod
    c = factorial(N-K) % mod
    return (a * pow(b, mod-2, mod) * pow(c, mod-2, mod)) % mod
v=Comb(A,k-2)
t=0
y=0
for i in range(1,n):
  t+=i*(n-i)*m*m%mod
for i in range(1,m):
  y+=i*(m-i)*n*n%mod

ans=v*(t+y)
print((ans%mod))
# Original solution
from itertools import combinations
import math
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


N,M,K = list(map(int,input().split()))
ans = 0
mod = 10**9 +7
by = cmb(N*M-2,K-2,mod)

#まずは、X軸の総和を求める。
for i in range(N):
    for j in range(M):
        cnt = M-j-1
        add = (((j+1)+(M-1))*cnt//2 - j*cnt)*N%mod
        ans += add*by%mod
        ans %= mod

for i in range(M):
    for j in range(N):
        cnt = N-j-1
        add = (((j+1)+(N-1))*cnt//2 - j*cnt)*M%mod
        ans += add*by%mod
        ans %= mod


print(ans)

# Optimized solution
"""
基本の方針は「各マンハッタン距離が何回足されるか」という考え方で距離の値を積み上げて行けばよい

まず、XとYは独立に考えることにする。
X軸の距離の方から積み上げる。
X1とX2の距離が足される回数は、
A.X1の列とX2の列の座標の組み合わせの数　×　B.その組み合わせが含まれるような座標の組み合わせの数
である。
A　＝　行数**２
B　＝　CMB(N*M-2 , K-2)である

同様の計算をY軸に関しても行えばよい。
"""
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

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

ans = 0

#X軸の距離を考える
A = M*M
B = cmb(N*M-2,K-2,p)
for i in range(1,N):
    ans += ((i*i)-(i-1+0)*i//2)*A*B%p
    ans %= p

#Y軸の距離を考える
A = N*N
B = cmb(N*M-2,K-2,p)
for i in range(1,M):
    ans += ((i*i)-(i-1+0)*i//2)*A*B%p
    ans %= p

print(ans)
# Original solution
import sys
mod = pow(10, 9) + 7
def C(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
NNN = (10**6)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range(2, NNN+1):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
n,m,k=list(map(int,input().split()))
#n=m=k=2
print((C(n*m,k)*C(k,2)%mod*(n+m)*inverse[3]%mod))


# Optimized solution
N, M, K = list(map(int, input().split()))
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1	 : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

def modinv(a):
    b, u, v = mod, 1, 0
    while b:
        t = a//b
        a, u = a-t*b, u-t*v
        a, b, u, v = b, a, v, u
    u %= mod
    return u

def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NNN = (10**6)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def f(n, m):
    x = m*m%mod
    y = (n*n*(n-1)//2 - n*(n-1)*(2*n-1)//6) % mod
    return x*y%mod

print((mul(f(N, M) + f(M, N), cmb(N*M-2, K-2))))
# Original solution
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


def cmb(n, r):
    r = min(r, n-r)
    if r == 0:
        return 1
    if r == 1:
        return n

    numer = [n - r + k + 1 for k in range(r)]
    denom = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denom[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numer[k - offset] /= pivot
                denom[k] /= pivot

    result = 1
    for k in range(r):
        if numer[k] > 1:
            result *= int(numer[k])

    return result


def solve(N: int, M: int, K: int):

    sx = 0
    for x in range(1, M+1):
        sx += x*(x-1)//2
        sx %= MOD
    sx *= N*N
    sx %= MOD

    sy = 0
    for y in range(1, N+1):
        sy += y*(y-1)//2
        sy %= MOD
    sy *= M*M
    sy %= MOD

    s = (sx+sy) % MOD
    s = (s*cmb(N*M-2, K-2)) % MOD
    print(s)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, M, K)


if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


def cmb(n, r):
    r = min(r, n-r)
    if r == 0:
        return 1
    if r == 1:
        return n

    numer = [n - r + k + 1 for k in range(r)]
    denom = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denom[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numer[k - offset] /= pivot
                denom[k] /= pivot

    result = 1
    for k in range(r):
        if numer[k] > 1:
            result *= int(numer[k])
            result %= MOD

    return result


def solve(N: int, M: int, K: int):

    sx = (M*(M+1)*(M-1)//6) % MOD
    sx = (sx * N*N) % MOD
    sy = (N*(N+1)*(N-1)//6) % MOD
    sy = (sy * M*M) % MOD
    s = (sx + sy) % MOD
    s = (s*cmb(N*M-2, K-2)) % MOD
    print(s)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, M, K)


if __name__ == '__main__':
    main()
# Original solution
MAX = 10**9 + 7

def mod_inv(i, MOD):
    return pow(i, MOD-2, MOD)

def combination(_N, _K):
    if _K > (_N/2):
        _K = _N - _K
    up = 1
    low = 1
    for i in range (_K):
        up *= (_N - i) % MAX
        low *= (i + 1) % MAX
    ret = up * mod_inv(low, MAX)
    if ret >= MAX:
        ret %= MAX
    return ret

def solve():
    N, M, K = [int(_) for _ in input().split()]
    disSum = (M*N* ((M*(N+1)*(N-1))%MAX + (N*(M+1)*(M-1)) % MAX)) % MAX
    disSum *= mod_inv(6, MAX)
    if disSum >= MAX:
        disSum %= MAX
    ret = disSum * combination(M*N-2, K-2)
    if ret >= MAX:
        ret %= MAX
    print(ret)

if __name__ == '__main__':
    solve()


# Optimized solution
MAX = 10**9 + 7

def mod_inv(i, mod):
    return pow(i, mod-2, mod)

def combination(_N, _K):
    if _K > (_N/2):
        _K = _N - _K
    up = 1
    low = 1
    for i in range (_K):
        up = up * (_N - i) % MAX
        low = low * (i + 1) % MAX
    ret = up * mod_inv(low, MAX) % MAX
    return ret

def solve():
    N, M, K = [int(_) for _ in input().split()]
    disSum = (M*N* ((M*(N+1)*(N-1))%MAX + (N*(M+1)*(M-1)) % MAX)) % MAX
    disSum *= mod_inv(6, MAX) % MAX
    ret = disSum * combination(M*N-2, K-2) % MAX
    print(ret)

if __name__ == '__main__':
    solve()
# Original solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, K = list(map(int, readline().split()))

    COM_MAX = N * M

    fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
    fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1

    for i in range(2, COM_MAX + 1):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    def com(n, r):
        if n < 0 or r < 0 or n < r:
            return 0
        return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD

    def solve(n, m, k):
        ans = 0
        for j in range(1, k):
            tmp = 0
            for i in range(1, n):
                tmp = (tmp + com(m * i, j) * com(m * (n - i), k - j)) % MOD
            ans = (ans + tmp * j * (k - j)) % MOD

        return ans

    ans = (solve(N, M, K) + solve(M, N, K)) % MOD
    print(ans)
    return


if __name__ == '__main__':
    main()


# Optimized solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, K = list(map(int, readline().split()))

    COM_MAX = N * M

    fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
    fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1

    for i in range(2, COM_MAX + 1):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    def com(n, r):
        if n < 0 or r < 0 or n < r:
            return 0
        return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD

    def solve(n, m, k):
        ans = 0
        for d in range(1, n):
            ans = (ans + com(n * m - 2, k - 2) * (m ** 2) * (n - d) * d) % MOD

        return ans

    ans = (solve(N, M, K) + solve(M, N, K)) % MOD
    print(ans)
    return


if __name__ == '__main__':
    main()
# Original solution
n,m,k=list(map(int,input().split()))
mod=10**9+7
import math
def f(x):
  return math.factorial(x)
def c(x,y):
  return f(x)//(f(x-y)*f(y))

ans=(n**2*(m-1)*m*(m+1)//6)%mod
ans=(ans+m**2*(n-1)*n*(n+1)//6)%mod
ans=(ans*c(m*n-2,k-2))%mod
print(ans)

# Optimized solution
n,m,k=list(map(int,input().split()))
import math
def f(x): return math.factorial(x)
def c(x,y): return f(x)//(f(x-y)*f(y))
print((((n**2*(m-1)*m*(m+1)//6+m**2*(n-1)*n*(n+1)//6)*c(m*n-2,k-2))%(10**9+7)))
# Original solution
import sys
sys.setrecursionlimit(100000)
while True:
  n,m,h,k = list(map(int,input().split()))
  if not n: break
  s_lst = [int(eval(input())) for _ in range(n)]
  b_lst = [tuple(map(int,input().split())) for _ in range(m)]
  b_lst = sorted(b_lst,key=lambda x:-x[1])
  def amida(b_lst, s_lst, used, k):
    if not b_lst:
      return sum(s_lst[0:k])
    elif used:
      for bar in b_lst:
        a = bar[0]
        temp = s_lst[a]
        s_lst[a] = s_lst[a - 1]
        s_lst[a - 1] = temp
      return sum(s_lst[0:k])
    else:
      save_s_lst = [i for i in s_lst]
      a = b_lst[0][0]
      temp = s_lst[a]
      s_lst[a] = s_lst[a - 1]
      s_lst[a - 1] = temp
      return min(amida(b_lst[1:], s_lst, 0, k), amida(b_lst[1:], save_s_lst, 1, k))

  print((amida(b_lst, s_lst, 0, k)))



# Optimized solution
while True:
  n,m,h,k = list(map(int,input().split()))
  if not n: break
  s_lst = [int(eval(input())) for _ in range(n)]
  i_lst = [i for i in range(n)]
  b_lst = [tuple(map(int,input().split())) for _ in range(m)]
  b_lst = sorted(b_lst,key=lambda x:x[1])
  pare_lst = []
  for bar in b_lst:
    ind = bar[0]
    temp = i_lst[ind]
    i_lst[ind] = i_lst[ind - 1]
    i_lst[ind - 1] = temp
    pare_lst.append((i_lst[ind], i_lst[ind - 1]))
#  print(i_lst)
  new_s_lst = [0] * n
  for i in range(n):
    new_s_lst[i_lst[i]] = s_lst[i]
#  print(s_lst)
  ans = sum(new_s_lst[:k])
#  print(ans)
#  print(pare_lst)
  max_dec = 0
  for pare in pare_lst:
    a = pare[0]
    b = pare[1]
#    print(a,b,s_lst[a],s_lst[b])
    if a < k and b >= k and new_s_lst[a] - new_s_lst[b] > max_dec:
      max_dec = new_s_lst[a] - new_s_lst[b]
    if b < k and a >= k and new_s_lst[b] - new_s_lst[a] > max_dec:
      max_dec = new_s_lst[b] - new_s_lst[a]
  print((ans - max_dec))
# Original solution
while True:
    n, m, h, k = list(map(int, input().split()))
    if not n:
        break
    points = [int(eval(input())) for _ in range(n)]
    bars = [tuple(map(int, input().split())) for _ in range(m)]
    bars_h = [set() for _ in range(h)]
    for ba, bh in bars:
        bars_h[bh].add(ba - 1)
    swap = [points] + [None] * m
    pattern = 1

    for i in range(h - 1, 0, -1):
        for ba in bars_h[i]:
            swap[pattern] = swap[0][:]
            for s in swap[:pattern]:
                s[ba], s[ba + 1] = s[ba + 1], s[ba]
            pattern += 1

    print((min(sum(s[:k]) for s in swap)))

# Optimized solution
while True:
    n, m, h, k = list(map(int, input().split()))
    if not n:
        break
    points = [int(eval(input())) for _ in range(n)]
    bars = [tuple(map(int, input().split())) for _ in range(m)]
    bars_h = [set() for _ in range(h)]
    for ba, bh in bars:
        bars_h[bh].add(ba - 1)
    swap = list(range(n))
    history = set()

    for i in range(h - 1, 0, -1):
        for ba in bars_h[i]:
            l, r = swap[ba:ba + 2]
            history.add((l, r) if l < r else (r, l))
            swap[ba:ba + 2] = r, l
    swap_dict = {v: i for i, v in enumerate(swap)}
    min_score_d = 0
    for l, r in history:
        li, ri = swap_dict[l], swap_dict[r]
        if li > ri:
            l, r, li, ri = r, l, ri, li
        if li < k and k <= ri:
            min_score_d = min(min_score_d, points[r] - points[l])

    print((sum(points[x] for x in swap[:k]) + min_score_d))
# Original solution
import sys
input=sys.stdin.readline
import copy
def knapsack(N,W,weight,value):
  dp=[[999999999999 for i in range(W+1)] for j in range(N+1)]
  dp2=[[set() for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0
 
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w:
        if dp[i][w-weight[i]]+value[i]>dp[i][w]:
          dp[i+1][w]=dp[i][w-weight[i]]+value[i]
          x=copy.copy(dp2[i][w-weight[i]])
          x.add(i)
          dp2[i+1][w]=x
        else:
          dp[i+1][w]=dp[i][w]
          dp2[i+1][w]=dp2[i][w]
        
      else:
        dp[i+1][w]=dp[i][w]
        dp2[i+1][w]=dp2[i][w]
  return [dp[N][W],dp2[N][W]]
 
n,t=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(n)]
a=[];b=[]
for i in range(n):
  a.append(l[i][0])
  b.append(l[i][1])
z=knapsack(n,t-1,a,b)
x=z[0];y=z[1]
M=[]
for i in range(n):
  if i not in y:
    M.append(b[i])
if len(M)==0:
  print(x)
else:
  print((x+max(M)))

# Optimized solution
import sys
input=sys.stdin.readline
import copy
def knapsack(N,W,weight,value):
  dp=[[999999999999 for i in range(W+1)] for j in range(N+1)]
  dp2=[]
  for i in range(N+1):
    x=[]
    for j in range(W+1):
      x.append([])
    dp2.append(x)
  for i in range(W+1): dp[0][i]=0
 
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w:
        if dp[i][w-weight[i]]+value[i]>dp[i][w]:
          dp[i+1][w]=dp[i][w-weight[i]]+value[i]
          x=copy.copy(dp2[i][w-weight[i]])
          x.append(i)
          dp2[i+1][w]=x
        else:
          dp[i+1][w]=dp[i][w]
          dp2[i+1][w]=dp2[i][w]
        
      else:
        dp[i+1][w]=dp[i][w]
        dp2[i+1][w]=dp2[i][w]
  return [dp[N][W],dp2[N][W]]
 
n,t=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(n)]
a=[];b=[]
for i in range(n):
  a.append(l[i][0])
  b.append(l[i][1])
z=knapsack(n,t-1,a,b)
x=z[0];y=z[1]
L=[0 for i in range(n)]
m=0
for i in range(len(y)):
  L[y[i]]=1
M=[]
for i in range(n):
  if L[i]==0:
    M.append(b[i])
if len(M)==0:
  print(x)
else:
  print((x+max(M)))
# Original solution
import sys
input=sys.stdin.readline
import copy
def knapsack(N,W,weight,value):
  dp=[[999999999999 for i in range(W+1)] for j in range(N+1)]
  dp2=[]
  for i in range(N+1):
    x=[]
    for j in range(W+1):
      x.append([])
    dp2.append(x)
  for i in range(W+1): dp[0][i]=0
 
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w:
        if dp[i][w-weight[i]]+value[i]>dp[i][w]:
          dp[i+1][w]=dp[i][w-weight[i]]+value[i]
          x=copy.copy(dp2[i][w-weight[i]])
          x.append(i)
          dp2[i+1][w]=x
        else:
          dp[i+1][w]=dp[i][w]
          dp2[i+1][w]=dp2[i][w]
        
      else:
        dp[i+1][w]=dp[i][w]
        dp2[i+1][w]=dp2[i][w]
  return [dp[N][W],dp2[N][W]]
 
n,t=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(n)]
a=[];b=[]
for i in range(n):
  a.append(l[i][0])
  b.append(l[i][1])
z=knapsack(n,t-1,a,b)
x=z[0];y=z[1]
L=[0 for i in range(n)]
m=0
for i in range(len(y)):
  L[y[i]]=1
M=[]
for i in range(n):
  if L[i]==0:
    M.append(b[i])
if len(M)==0:
  print(x)
else:
  print((x+max(M)))

# Optimized solution
import sys
input=sys.stdin.readline
import copy
def knapsack(N,W,weight,value):
  dp=[[999999999999 for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0
 
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w:
        if dp[i][w-weight[i]]+value[i]>dp[i][w]:
          dp[i+1][w]=dp[i][w-weight[i]]+value[i]
        else:
          dp[i+1][w]=dp[i][w]
      else:
        dp[i+1][w]=dp[i][w]
  return dp
 
n,t=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
a=[];b=[]
for i in range(n):
  a.append(l[i][0])
  b.append(l[i][1])
dp=knapsack(n,t-1,a,b)
ans=[]
for i in range(n):
  if i!=n:
    ans.append(dp[i][t-1]+b[i])
  else:
    ans.append(dp[n][t-i])
print((max(ans)))
# Original solution
import sys
input=sys.stdin.readline
def knapsack(N,W,weight,value):
  dp=[[float('inf') for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1):
    dp[0][i]=0
 
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w:
        if dp[i][w-weight[i]]+value[i]>dp[i][w]:
          dp[i+1][w]=dp[i][w-weight[i]]+value[i]
        else:
          dp[i+1][w]=dp[i][w]
      else:
        dp[i+1][w]=dp[i][w]
  return dp
 
n,t=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
a=[];b=[]
for i in range(n):
  a.append(l[i][0])
  b.append(l[i][1])
dp=knapsack(n,t-1,a,b)
ans=[]
for i in range(n):
  if i!=n:
    ans.append(dp[i][t-1]+b[i])
  else:
    ans.append(dp[n][t])
print((max(ans)))

# Optimized solution
import sys
input=sys.stdin.readline
def knapsack(N,W,weight,value):
  dp=[[999999999999 for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1):
    dp[0][i]=0
 
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w:
        if dp[i][w-weight[i]]+value[i]>dp[i][w]:
          dp[i+1][w]=dp[i][w-weight[i]]+value[i]
        else:
          dp[i+1][w]=dp[i][w]
      else:
        dp[i+1][w]=dp[i][w]
  return dp
 
n,t=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
a=[];b=[]
for i in range(n):
  a.append(l[i][0])
  b.append(l[i][1])
dp=knapsack(n,t-1,a,b)
ans=[]
for i in range(n):
  if i!=n:
    ans.append(dp[i][t-1]+b[i])
  else:
    ans.append(dp[n][t])
print((max(ans)))
# Original solution
import sys
input=sys.stdin.readline
import copy
def knapsack(N,W,weight,value):
  dp=[[999999999999 for i in range(W+1)] for j in range(N+1)]
  dp2=[[0 for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0
 
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w:
        if dp[i][w-weight[i]]+value[i]>dp[i][w]:
          dp[i+1][w]=dp[i][w-weight[i]]+value[i]
          dp2[i+1][w]=w-weight[i]
        else:
          dp[i+1][w]=dp[i][w]
          dp2[i+1][w]=w
        
      else:
        dp[i+1][w]=dp[i][w]
        dp2[i+1][w]=w
  
  l=[]
  x=W
  for i in range(n-1,-1,-1):
    if dp2[i+1][x]==x-weight[i]:
      l.append(i)
    x=dp2[i+1][x]
  return dp[N][W],l
 
n,t=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(n)]
a=[];b=[]
for i in range(n):
  a.append(l[i][0])
  b.append(l[i][1])
z=knapsack(n,t-1,a,b)
L=[0]*n
for i in range(len(z[1])):
  L[z[1][i]]=1
M=[]
for i in range(n):
  if L[i]==0:
    M.append(l[i][1])
if len(M)==0:
  print((z[0]))
else:
  print((z[0]+max(M)))

# Optimized solution
import sys
input=sys.stdin.readline
def knapsack(N,W,weight,value):
  dp=[[999999999999 for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1):
    dp[0][i]=0
 
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w:
        if dp[i][w-weight[i]]+value[i]>dp[i][w]:
          dp[i+1][w]=dp[i][w-weight[i]]+value[i]
        else:
          dp[i+1][w]=dp[i][w]
      else:
        dp[i+1][w]=dp[i][w]
  return dp
 
n,t=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
a=[];b=[]
for i in range(n):
  a.append(l[i][0])
  b.append(l[i][1])
dp=knapsack(n,t-1,a,b)
ans=[]
for i in range(n):
  if i!=n:
    ans.append(dp[i][t-1]+b[i])
  else:
    ans.append(dp[n][t])
print((max(ans)))
# Original solution
N,T=list(map(int,input().split()))
x=[None] # x[0]
for i in range(1,N+1): # x[i]のiに対応させる
    x.append(tuple(map(int,input().split()))) # x[1]~x[N]
# print(x) #DB★

dp1=[[0 for j in range(T)] for i in range(N+2)] # 0~N+1 dp1[i]はx[1]からx[i]まで使用（dp1[0]は使用するx[i]なしの初期値，dp1[N+1]は余り→0で初期化していることが後で役に立つ）
for i in range(1,N+1): # dp1[0]は初期値なのでいじらない。dp1[N+1]は余りなので計算しない。dp1[N]まで計算するので，iはNまで
    for j in range(T): # 0分後からT-1分後まで計算する
        if x[i][0]>j:
            dp1[i][j]=dp1[i-1][j]
        else:
            dp1[i][j]=max(dp1[i-1][j],dp1[i-1][j-x[i][0]]+x[i][1])

# print(dp1) #DB★

dp2=[[0 for j in range(T)] for i in range(N+2)] # 0~N+1 dp2[i]はx[i]からx[N]まで（x[N]からx[i]まで）使用（dp2[N+1]は使用するx[i]なしの初期値，dp2[0]は余り）
for i in range(N,0,-1): # dp2[N+1]は初期値なのでいじらない。dp2[0]は余りなので計算しない。dp2[1]まで計算するので，iは1まで
    for j in range(T):
        if x[i][0]>j:
            dp2[i][j]=dp2[i+1][j]
        else:
            dp2[i][j]=max(dp2[i+1][j],dp2[i+1][j-x[i][0]]+x[i][1])

# print(dp2) #DB★

cans=[0 for i in range(N+1)] # i番目の料理を最後に食べる場合の満足度の最大値
for i in range(1,N+1):
    cans[i]=max([dp1[i-1][j]+dp2[i+1][T-1-j] for j in range(T)])+x[i][1]

# print(cans) #DB★ 

ans=max(cans)

print(ans)

# Optimized solution
N,T=list(map(int,input().split()))
x=[(0,0)] # x[0]
for i in range(1,N+1): # x[i]のiに対応させる
    x.append(tuple(map(int,input().split()))) # x[1]~x[N]

x.sort()
# print(x) #DB★

dp1=[[0 for j in range(T)] for i in range(N+2)] # 0~N+1 dp1[i]はx[1]からx[i]まで使用（dp1[0]は使用するx[i]なしの初期値，dp1[N+1]は余り→0で初期化していることが後で役に立つ）
for i in range(1,N+1): # dp1[0]は初期値なのでいじらない。dp1[N+1]は余りなので計算しない。dp1[N]まで計算するので，iはNまで
    for j in range(T): # 0分後からT-1分後まで計算する
        if x[i][0]>j:
            dp1[i][j]=dp1[i-1][j]
        else:
            dp1[i][j]=max(dp1[i-1][j],dp1[i-1][j-x[i][0]]+x[i][1])

cans=[dp1[i-1][T-1]+x[i][1] for i in range(1,N+1)]

# print(cans) #DB★ 

ans=max(cans)

print(ans)