Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02892 (python)

Fixed submission:
from sys import stdin
import sys
#import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##
def main():
    N = ri()
    S = [""] * N
    for i in range(N): S[i] = rs()

    bw = [-1] * N
    q = collections.deque()
    bw[0] = 0
    q.append(0)
    while(len(q) > 0):
        now = q.popleft()
        for nxt in range(N):
            if S[now][nxt] == '0': continue
            if bw[nxt] == -1:
                bw[nxt] = bw[now] ^ 1
                q.append(nxt)
            elif bw[nxt] == bw[now]:
                print(-1)
                sys.exit(0)
    
    inf = int(1e9)
    wf = [[inf] * N for i in range(N)]
    for i in range(N):
        for j in range(N):
            wf[i][j] = 1 if S[i][j] == '1' else inf
            if i == j: wf[i][j] = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])
    
    ma = 0
    for i in range(N):
        for j in range(N):
            ma = max(ma, wf[i][j])

    print(ma + 1)

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##
def main():
    N = ri()
    S = [""] * N
    for i in range(N): S[i] = rs()

    bw = [-1] * N
    q = collections.deque()
    bw[0] = 0
    q.append(0)
    while(len(q) > 0):
        now = q.popleft()
        for nxt in range(N):
            if S[now][nxt] == '0': continue
            if bw[nxt] == -1:
                bw[nxt] = bw[now] ^ 1
                q.append(nxt)
            elif bw[nxt] == bw[now]:
                print(-1)
                sys.exit(0)
    
    inf = int(1e9)
    wf = [[inf] * N for i in range(N)]
    for i in range(N):
        for j in range(N):
            wf[i][j] = 1 if S[i][j] == '1' else inf
    for k in range(N):
        for i in range(N):
            for j in range(N):
                wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])
    
    ma = 0
    for i in range(N):
        for j in range(N):
            ma = max(ma, wf[i][j])

    print(ma + 1)

if __name__ == "__main__":
    main()
Problem p03053 (python)

Fixed submission:
from sys import stdin
import sys
import collections


##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##
def main():
    H, W = rip()
    S = [rs() for i in range(H)]
    #min = np.full((H,W),-1, dtype = 'int')
    min = [[-1] * W for i in range(H)]
    q = collections.deque()
    def enc(h, w): return h * W + w
    def inRange(t, l, r): return l <= t and t < r
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]

    for i in range(H):
        for j in range(W):
            if S[i][j] == '#':
                q.append(enc(i,j))
                min[i][j] = 0
    while(len(q) > 0):
        rc = q.popleft()
        y = rc // W
        x = rc % W
        for t in range(4):
            nx = x + dx[t]
            ny = y + dy[t]
            if (not inRange(nx,0,W)) or (not inRange(ny,0,H)): continue
            if min[ny][nx] == -1:
                min[ny][nx] = min[y][x] + 1
                q.append(enc(ny,nx))
    
    ma = 0
    for i in range(H):
        for j in range(W):
            ma = max(ma, min[i][j])
    print(ma)





if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from sys import stdin
import sys
import collections
import numpy as np

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##
def main():
    H, W = rip()
    S = [rs() for i in range(H)]
    min = np.full((H,W),-1, dtype = 'int')
    q = collections.deque()
    def enc(h, w): return h * W + w
    def inRange(t, l, r): return l <= t and t < r
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]

    for i in range(H):
        for j in range(W):
            if S[i][j] == '#':
                q.append(enc(i,j))
                min[i][j] = 0
    while(len(q) > 0):
        rc = q.popleft()
        y = rc // W
        x = rc % W
        for t in range(4):
            nx = x + dx[t]
            ny = y + dy[t]
            if (not inRange(nx,0,W)) or (not inRange(ny,0,H)): continue
            if min[ny][nx] == -1:
                min[ny][nx] = min[y][x] + 1
                q.append(enc(ny,nx))
    
    ma = 0
    for i in range(H):
        for j in range(W):
            ma = max(ma, min[i][j])
    print(ma)





if __name__ == "__main__":
    main()
Problem p02933 (python)

Fixed submission:
import numpy

A = int(input())
S = input()

if A >= 3200:
    print(S)
else:
    print("red")

Buggy submission (verdict: Runtime Error):
A = int(input())
S = input()

if A >= 3200:
    print(S)
else:
    print("red")

Buggy submission (verdict: Runtime Error):
import numpy

A = int(input())
S = input()

if A >= 3200:
    print(S)
else:
    print("red")
Problem p02685 (python)

Fixed submission:
n, m, k = map(int, input().split())


class Combination:
    """
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv


mod = 998244353
total = 0
comb = Combination(n, mod)

v2 = [0] * (k+1)
v2[k] = (m * pow(m-1, n-k-1, mod)) % mod
for i in range(k-1, -1, -1):
    v2[i] = (v2[i+1] * (m-1)) % mod

for i in range(k+1):
    v = comb(n-1, i)
    total += (v * v2[i]) % mod
    total %= mod

print(total)

Buggy submission (verdict: Runtime Error):
n, m, k = map(int, input().split())


class Combination:
    """
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv


mod = 998244353
total = 0
comb = Combination(n-1, mod)

v2 = [0] * (k+1)
v2[k] = (m * pow(m-1, n-k-1, mod)) % mod
for i in range(k-1, -1, -1):
    v2[i] = (v2[i+1] * (m-1)) % mod

for i in range(k+1):
    v = comb(n-1, i)
    total += (v * v2[i]) % mod
    total %= mod

print(total)
Problem p03045 (python)

Fixed submission:
from collections import Counter


class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    def get_size(self, x):
        x = self.find(x)
        return self.size[x]


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

uf = UnionFind(n)
for i in range(m):
    x, y, z = map(int, input().split())
    uf.union(x-1, y-1)

c = Counter([uf.find(i) for i in range(n)])
print(len(c))

Buggy submission (verdict: Runtime Error):
import networkx as nx

n, m = map(int, input().split())
g = nx.Graph()
g.add_nodes_from(range(1, n+1))
for i in range(m):
    x, y, z = map(int, input().split())
    g.add_edge(x, y)
print(nx.number_connected_components(g))
Problem p02659 (python)

Fixed submission:
import decimal

a, b = input().split()

a = int(a)
b = decimal.Decimal(b)
b *= 100

ans = a * b

ans //= 100

print(ans)

Buggy submission (verdict: Runtime Error):
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <numeric>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

int main(void)
{
    ll a;
    double b;
    cin >> a >> b;
    ll y = ceil(b * 100.0);

    ll ans = a * y;

    ans /= 100;

    cout << ans << endl;
}
Problem p02793 (python)

Fixed submission:
from fractions import gcd
import math
n = int(input())
a = list(map(int, input().split()))
MOD=10**9+7
lcm=1
for i in range(n):
    lcm*=a[i]//gcd(lcm,a[i])
res=0
for i in range(n):
    res+=lcm//a[i]
print(res%MOD)

Buggy submission (verdict: Runtime Error):
from fractions import gcd
import math
n = int(input())
a = list(map(int, input().split()))
MOD=10**9+7
lcm=1
for i in range(n):
    lcm*=a[i]//math.gcd(lcm,a[i])
res=0
for i in range(n):
    res+=lcm//a[i]
print(res%MOD)
Problem p03327 (python)

Fixed submission:
n=int(input())
if(n>=1000):
  print("ABD")
else:
  print("ABC")

Buggy submission (verdict: Runtime Error):
n=int(input())
if(n>=1000):
  print("ABD")
 else:
  print("ABC")
Problem p03822 (python)

Fixed submission:
import sys
sys.setrecursionlimit(3000000)

n = int(input())

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

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

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

print(dfs(0)-1)

Buggy submission (verdict: Runtime Error):
n = int(input())

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

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

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

print(dfs(0))

Buggy submission (verdict: Runtime Error):
n = int(input())

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

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

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

print(dfs(0))
Problem p02735 (python)

Fixed submission:

h, w = map(int, input().split())
mp = [list(input()) for i in range(h)]
dp = [[0]*105 for _ in range(105)]
if mp[0][0]=='#':
    dp[0][0]+=1
for i in range(w-1):
    plus=0
    if mp[0][i+1]!=mp[0][i] and mp[0][i+1] == '#':
        plus=1
    dp[0][i+1] = dp[0][i]+plus
for i in range(h-1):
    plus=0
    if mp[i+1][0]!=mp[i][0] and mp[i+1][0] == '#':
        plus=1
    dp[i+1][0] = dp[i][0]+plus

for i in range(1,h):
    for j in range(1,w):
        plus=0
        plus2=0
        if mp[i][j]!=mp[i-1][j] and mp[i][j]=='#':
            plus=1
        if mp[i][j]!=mp[i][j-1] and mp[i][j]=='#':
            plus2=1
        dp[i][j] = min(dp[i-1][j]+plus, dp[i][j-1]+plus2)

print(dp[h-1][w-1])

Buggy submission (verdict: Runtime Error):

h, w = map(int, input().split())
mp = [list(input()) for i in range(h)]
dp = [[0]*105 for _ in range(105)]
if mp[0][0]=='#':
    dp[0][0]+=1
for i in range(w-1):
    plus=0
    if mp[0][i+1]=='#':
        plus=1
    dp[0][i+1] = dp[0][i]+plus
for i in range(h-1):
    plus=0
    if mp[i+1][0]=='#':
        plus=1
    dp[i+1][0] = dp[i][0]+plus

for i in range(1,w):
    for j in range(1,h):
        plus=0
        if mp[i][j]=='#':
            plus=1
        dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + plus

print(dp[h-1][w-1])
Problem p02873 (python)

Fixed submission:
s = input()
n = len(s)
list0 = list()
list2 = list()
ans = 0
for i in range(n-1):
    if s[i:i+2] == '><':
        list0.append(i+1)
    elif s[i:i+2] == '<>':
        list2.append(i+1)

if s[0] == '<':
    list0.insert(0, 0)
else:
    if len(list0):
        p1 = list0[0]
    else:
        p1 = n
    ans += 1/2 * p1 * (p1 + 1)



if s[-1] == '>':
    list0.append(n)
else:
    if len(list0):
        p1 = n - list0[-1]
    else:
        p1 = n
    ans += 1/2 * p1 * (p1 + 1)

for i in range(len(list2)):
    p1 = max(list2[i] - list0[i], list0[i+1] - list2[i])
    p2 = min(list2[i] - list0[i], list0[i+1] - list2[i])
    ans += 1/2 * p1 * (p1 + 1) + 1/2 * p2 * (p2 - 1)

print(int(ans))

Buggy submission (verdict: Runtime Error):
s = input()
n = len(s)
list0 = list()
list2 = list()
ans = 0
for i in range(n-1):
    if s[i:i+2] == '><':
        list0.append(i+1)
    elif s[i:i+2] == '<>':
        list2.append(i+1)

if s[0] == '<':
    list0.insert(0, 0)
else:
    p1 = list0[0]
    ans += 1/2 * p1 * (p1 + 1)


if s[-1] == '>':
    list0.append(n)
else:
    p1 = n - list0[-1]
    ans += 1/2 * p1 * (p1 + 1)

for i in range(len(list2)):
    p1 = max(list2[i] - list0[i], list0[i+1] - list2[i])
    p2 = min(list2[i] - list0[i], list0[i+1] - list2[i])
    ans += 1/2 * p1 * (p1 + 1) + 1/2 * p2 * (p2 - 1)

print(int(ans))
Problem p02695 (python)

Fixed submission:
from itertools import combinations_with_replacement
N, M, Q = map(int, input().split())
ABCD = [list(map(int, input().split())) for _ in range(Q)]
ans = 0
for t in combinations_with_replacement(range(1, M+1), N):
    an = 0
    for a, b, c, d in ABCD:
        if t[b-1]-t[a-1] == c:
            an += d
    if ans < an:
        ans = an
print(ans)

Buggy submission (verdict: Runtime Error):
from itertools import combinations_with_replacement
N, M, Q = map(int, input().split())
ABCD = [list(map(int, input().split())) for _ in range(Q)]
ans = 0
for t in combinations_with_replacement(range(1, M+1), N):
    an = 0
    for a, b, c, d in ABCD:
        if t[b-1]-t[a-1] == c:
            an += d
    if ans < an:
        ans = an
print(an
Problem p02816 (python)

Fixed submission:
def z_algo(S):
    # Z-algoirhm  O(n)
    # Z[i] := S と S[i:] で prefix が何文字一致しているか
    # 検証: https://atcoder.jp/contests/arc055/submissions/14179788
    i, j, n = 1, 0, len(S)
    Z = [0] * n
    Z[0] = n
    while i < n:
        while i+j < n and S[j] == S[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        Z[i] = j
        d = 1
        while i+d < n and d+Z[d] < j:
            Z[i+d] = Z[d]
            d += 1
        i += d
        j -= d
    return Z


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A_diff = []
a2 = A[-1]
for a in A:
    A_diff.append(a^a2)
    a2 = a
B_diff = []
b2 = B[-1]
for b in B:
    B_diff.append(b^b2)
    b2 = b
A_diff_2 = A_diff + A_diff[:-1]
Z = z_algo(A_diff_2)
A_diff_str = "_".join(map(str, A_diff_2))
B_diff_str = "_".join(map(str, B_diff))
idx = A_diff_str.find(B_diff_str)
if idx==-1:
    exit()
idx = A_diff_str[:idx].count("_")
Ans = []
b0 = B[-idx]
for i, (z, a, b) in enumerate(zip(Z, A, B)):
    if z >= N:
        Ans.append([(idx+i)%N, a^b0])
        # x = [idx, i, a, b, B[-idx]]
        # print(x)
Ans.sort()  # これいる？
for k, x in Ans:
    print(f"{k} {x}")

Buggy submission (verdict: Runtime Error):
# この方針かしこい

import os
import sys
import numpy as np

def z_algo(S):
    # Z-algoirhm  O(n)
    # Z[i] := S と S[i:] で prefix が何文字一致しているか
    # 検証: https://atcoder.jp/contests/arc055/submissions/14179788
    i, j, n = 1, 0, len(S)
    Z = np.zeros_like(S)
    Z[0] = n
    while i < n:
        while i+j < n and S[j] == S[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        Z[i] = j
        d = 1
        while i+d < n and d+Z[d] < j:
            Z[i+d] = Z[d]
            d += 1
        i += d
        j -= d
    return Z

def solve(N, A, B):
    Diff = np.empty(3*N, dtype=np.int64)
    Diff[0] = B[0] ^ B[-1]
    Diff[1:N] = B[1:] ^ B[:-1]
    Diff[N] = Diff[2*N] = A[0] ^ A[-1]
    Diff[N+1:2*N] = Diff[2*N+1:3*N] = A[1:] ^ A[:-1]
    Z = z_algo(Diff)[N:2*N]
    Ans = [(0,0)]*0
    for i in range(N):
        z = Z[i]
        if z >= N:
            Ans.append((i, B[0]^A[i]))
    return np.array(Ans)


# >>> numba compile >>>
numba_config = [
    [z_algo, "i8[:](i8[:])"],
    [solve, "i8[:,:](i8,i8[:],i8[:])"],
]
if sys.argv[-1] == "ONLINE_JUDGE":
    from numba import njit
    from numba.pycc import CC
    cc = CC("my_module")
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature)(func)
        cc.export(func.__name__, signature)(func)
    cc.compile()
    exit()
elif os.name == "posix":
    exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
else:
    from numba import njit
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature, cache=True)(func)
    print("compiled!", file=sys.stderr)
# <<< numba compile <<<


def main():
    N = int(input())
    A = np.array(input().split(), dtype=np.int64)
    B = np.array(input().split(), dtype=np.int64)
    Ans = solve(N, A, B).tolist()
    print("\n".join(map(lambda x: " ".join(map(str, x)), Ans)))

main()
Problem p02863 (python)

Fixed submission:
import sys
sys.setrecursionlimit(500000)

def knapsack(VW, limit):
    n = len(VW)
    dp = [[0] * (limit+1) for _ in range(n+1)]
    for idx, (v, w) in enumerate(VW, 1):
        for we in range(limit+1):
            dp[idx][we] = dp[idx-1][we]
            if we >= w:
                dp[idx][we] = max(dp[idx][we], dp[idx-1][we-w]+v)
    return dp

def main():
    N, T = map(int, input().split())
    VW = []
    ma = 0
    ama = -1
    for i in range(N):
        w, v = map(int, input().split())
        if ma < v:
            ma = v
            ama = i
        VW.append([v, w])
    dp1 = knapsack(VW, T-1)
    VW.reverse()
    dp2 = knapsack(VW, T-1)
    dp2.reverse()
    VW.reverse()
    #for d in dp2:
    #    print(d)
    ans = 0
    for (v, w), d1, d2 in zip(VW, dp1[:-1], dp2[1:]):
        #print(v, w, d1, d2)
        for i in range(1, T):
            d1[i] = max(d1[i], d1[i-1])
            d2[i] = max(d2[i], d2[i-1])
        for dd1, dd2 in zip(d1, d2[::-1]):
            ans = max(ans, dd1+dd2+v)
    print(ans)


main()

Buggy submission (verdict: Runtime Error):
# 枝刈り探索（分枝限定法）

class Knapsack:
    def __init__(self, VW):
        self.VW = VW
        self.VW.sort(key=lambda vw: vw[0] / vw[1], reverse=True)
        self.n = len(VW)

    def solve(self, capacity, ok=0):
        self.ok = ok
        self.capacity = capacity
        return self._dfs(0, 0, 0)

    def _dfs(self, i, v_now, w_now):
        if i == self.n:
            self.ok = max(self.ok, v_now)
            return v_now
        ng, f = self._solve_relaxation(i, self.capacity - w_now)
        ng += v_now
        if f:
            self.ok = max(self.ok, ng)
            return ng
        if ng < self.ok:
            return -float("inf")
        res = -float("inf")
        v, w = self.VW[i]
        if w_now + w <= self.capacity:
            res = max(res, self._dfs(i + 1, v_now + v, w_now + w))
        res = max(res, self._dfs(i + 1, v_now, w_now))
        return res

    def _solve_relaxation(self, i, capacity):
        res = 0
        f = True
        for v, w in self.VW[i:]:
            if capacity == 0:
                break
            if w <= capacity:
                capacity -= w
                res += v
            else:
                f = False
                res += v * (capacity / w)
                break
        return res, f


def main():
    N, T = map(int, input().split())
    VW = []
    ma = 0
    ama = -1
    for i in range(N):
        w, v = map(int, input().split())
        if ma < v:
            ma = v
            ama = i
        VW.append([v, w])
    del VW[ama]
    if N==1:
        print(ma)
        exit()
    knapsack = Knapsack(VW)
    print(knapsack.solve(T-1) + ma)


main()