Harryxun/stf_run huggingface dataset:
# coding: utf-8
from functools import lru_cache
import sys


def solve(*args: str) -> str:
    n = int(args[0])
    LR = []
    for a in args[1:]:
        LR.append(tuple(map(int, a.split())))

    dp = DP(LR)

    sys.setrecursionlimit(10**5)
    return str(dp.search_max(0, 0, 10**9, 0, 10**9))


class DP:
    def __init__(self, LR: list):
        self.LR = LR

    @lru_cache(maxsize=None)
    def search_max(self, index: int, l1: int, r1: int, l2: int, r2: int)\
            -> int:
        ret = 0

        if index < len(self.LR):
            l, r = self.LR[index]
            ret = max(
                self.search_max(index+1, max(l, l1), min(r, r1), l2, r2),
                self.search_max(index+1, l1, r1, max(l, l2), min(r, r2))
            )
        else:
            if l1 == 0 or l2 == 0:
                ret = 0
            else:
                ret = max(0, (r1-l1)) + max(0, (r2-l2) + 2)

        return ret


if __name__ == "__main__":
    n = input()
    print(solve(*([n]+[input() for _ in range(int(n))])))


### FIXED CODE ###

# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n = int(args[0])
    LR = [tuple(map(int, a.split())) for a in args[1:]]
    L, R = zip(*LR)

    ret = 0

    p, q = np.argmax(L), np.argmin(R)
    lp, rq = L[p], R[q]

    ret = max(0, 1+rq-lp) + max(0, max(1+r-l for l, r in LR))

    AB = [[max(0, 1+r-lp), max(0, 1+rq-l)] for l, r in LR]
    AB.sort(key=lambda x: (x[0], -x[1]))
    A, B = map(list, zip(*AB))

    # for i in range(1, n):
    #     ret = max(ret, min(A[i:]) + min(B[:i]))
    b_min = 1+10**9
    for i in range(n-1):
        b_min = min(b_min, B[i])
        ret = max(ret, b_min + A[i+1])

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
while 1:
 H,W = map(int, raw_input().split())
 if h == w == 0:
  break
 else:
  print '#'*w
  for i in range(h-2):
   if w >= 2:
    print '#'+'.'*(w-2)+'#'
   else:
    print '#'
  print '#'*w

### FIXED CODE ###

while True:
 H, W = map(int, raw_input().split())
 if (H+W) == 0:
  break
 print "#"*W
 for h in range(1, (H-1)):
  print  "#" + ('.'*(W-2)) + "#"
 print "#"*W
 print ""
N, M = map(int, input().split())
for _ in range(M):
    a, b = input().split()
for _ in range(1, N+1):
    print(a.count("i")+b.count("i")



### FIXED CODE ###

n, m = map(int, input().split())
a, b = [0]*m, [0]*m
for i in range(m):
    a[i], b[i] = map(int, input().split())
for j in range(1,n+1):
    print(a.count(j)+b.count(j))
n = int(input())
d = list(map(int,input().split()))

total = 0

for i in range(d.count()-1):
    for j in range(1,d.count()):
        total += d[i]*d[j]


print(total)

### FIXED CODE ###

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

total = 0

for i in range(0,len(d)-1):
    for j in range(i+1,len(d)):
        total += d[i]*d[j]
print(total)
a,b,c,d=map(int,input().split())
if a+b>c+d:
    print("Left")
elif a+b=c+d:
    print("Balanced")
else:
    print("Right")        

### FIXED CODE ###

a, b, c, d = map(int, input().split())
l = a + b
r = c + d
if l > r:
    print("Left")
elif l == r:
    print("Balanced")
else:
    print("Right")
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, W;
    cin >> N >> W;

    vector<int> dp = vector<int>(W + 1, 0);
    vector<int> idx = vector<int>(1, 0);
    int ans = 0;

    for (int i = 0; i < N; i++) {
        int w, v;
        cin >> w >> v;
        vector<int> new_idx = vector<int>(1, 0);
        for (const auto& k : idx) {
            if (k + w <= W) {
                dp[k + w] = max(dp[k + w], dp[k] + v);
                new_idx.push_back(k + w);
                ans = max(ans, dp[k + w]);
            }
        }
        idx.insert(idx.end(), new_idx.begin(), new_idx.end());
    }

    cout << ans << endl;
}

### FIXED CODE ###

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

dp = [0] * (W + 1)
weights2check = [0]
ans = 0
for _ in range(N):
    w, v = map(int, input().split())
    for k in range(W-w, -1, -1):
        dp[k + w] = max(dp[k + w], dp[k] + v)
        ans = max(ans, dp[k + w])


print(ans)
n = int(input())
s = []
for i in range(n):
  tmp = str(input())
  tmp = "".join(sorted(tmp))
  s.append(tmp)
 
a = [0 for i in range(10**3)]
for i in range(2, 10**3):
  x = a[i-1] + (i-1)
  a[i] = x
 
# print("s:", s)
ans = 0
for _ in list(set(s)):
  ans+= a[s.count(_)]
  
print(ans)

### FIXED CODE ###

alphabet = "abcdefghijklmnopqrstuvwxyz"


n = int(input())
res = dict()
for _ in range(n):
    s = str(input())
    freqency = [0 for _ in alphabet]
    for __ in s:
        freqency[alphabet.index(__)] += 1
    freq = "".join([str(___) for ___ in freqency])
    if freq not in res:
        res[freq] = 1
    else:
        res[freq] += 1

ans = 0
for value in res.values():
    ans += ((value-1)*value)/2
  
print(int(ans))
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

s = sinput()
q = iinput()
cnt = 0
for i in range(q):
    try: t,f,c = sarr()
    except: cnt += 1; cnt %= 2; continue
    print("====", t,f,c)
    if cnt:
        if f == 1: s = s + c
        if f == 2: s = c + s
    else:
        if f == 1: s = c + s
        if f == 2: s = s + c
    print(s)

s = s[::-1] if cnt else s
print(s)


### FIXED CODE ###

import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

s = col.deque(sinput().split())
q = iinput()
cnt = 0
for i in range(q):
    try: t,f,c = sarr()
    except: cnt += 1; cnt %= 2; continue
    if cnt: #反転の状態
        if f == "1": s.append(c)
        if f == "2": s.appendleft(c)
    else: #ノーマル状態
        if f == "1": s.appendleft(c)
        if f == "2": s.append(c)
    #print(s)

s = "".join(s)
s = s[::-1] if cnt else s
print(s)
import sympy

n = int(input())
ans = 0
for i in range(1, n + 1):
    ans += i * len(sympy.divisors(i))
print(ans)    

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1, n+1):
    ans += (i+(n-n%i))*(n//i)//2
print(ans)
try:
 total=s=i=0 
 while True:
  a,b = map(int,input().split(','))
  total += a*b
  s += b
  i += 1
except:
 print(total)
 print(round(s/i+0.5 ))

### FIXED CODE ###

while True:
 try:
   a,b,c=map(float,input().split(','))
   bmi=b/c**2
   if bmi>=25:
     print(int(a))
 except:
  break
import math
import random

def is_prime3(q,k=50):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    for i in xrange(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True


a = int(input())
while True:
 if is_prime3(a) == 1:
  break
 a = a + 1

print(a)



### FIXED CODE ###

import random

def is_prime(n):
    if n == 2: return True
    if n == 1 or n & 1 == 0: return False

    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for k in range(100):
        a = random.randint(1, n - 1)
        t = d
        y = pow(a, t, n)

        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1

        if y != n - 1 and t & 1 == 0:
            return False

    return True

a = int(input())

while True:
 if is_prime(a) == 1:
  break
 a = a + 1

print(a)
N=int(input())

H=list(map(int,input().split()))
A=[0 for i in range(N)]
if H[0]>=H[1]:
  A[0]+=1
for i in range(1,N-1):
  if H[i]>=H[i+1]:
    A[i]+=A[i-1]+1
print(max(A))

### FIXED CODE ###

N=int(input())

H=list(map(int,input().split()))
A=[0 for i in range(N)]
if N==1:
  print(0)
else:
  if H[0]>=H[1]:
  	A[0]+=1
  if N>=3:
    for i in range(1,N-1):
      if H[i]>=H[i+1]:
        A[i]+=A[i-1]+1
  print(max(A))
def d_blue_and_red_balls(N, K, MOD=10**9 + 7):
    from math import factorial

    def comb(n, r):
        return factorial(n) // (factorial(r) * factorial(n - r))

    ans = [comb(N - K + 1, i) * comb(K - 1, i - 1) % MOD for i in range(1, K + 1)]
    return '\n'.join(map(str, ans))

N, K = [int(i) for i in input().split()]
print(d_blue_and_red_balls(N, K))

### FIXED CODE ###

def d_blue_and_red_balls(N, K, MOD=10**9 + 7):
    class Combination(object):
        """
        順列組み合わせ
        参考: https://harigami.net/contents?id=5f169f85-5707-4137-87a5-f0068749d9bb
        """
        __slots__ = ["mod", "factorial", "inverse"]

        def __init__(self, max_n: int = 10**6, mod: int = 10**9 + 7):
            fac, inv = [1], []
            fac_append, inv_append = fac.append, inv.append

            for i in range(1, max_n + 1):
                fac_append(fac[-1] * i % mod)

            inv_append(pow(fac[-1], mod - 2, mod))

            for i in range(max_n, 0, -1):
                inv_append(inv[-1] * i % mod)

            self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

        def combination(self, n, r):
            if r == n or r == 0:
                return 1
            if r > n:
                return 0
            return self.factorial[n] * self.inverse[r] * self.inverse[n - r] % self.mod

    comb = Combination(max(N - K + 1, K - 1))
    ans = [comb.combination(N - K + 1, i) * comb.combination(K - 1, i - 1) %
           MOD for i in range(1, K + 1)]
    return '\n'.join(map(str, ans))

N, K = [int(i) for i in input().split()]
print(d_blue_and_red_balls(N, K))
n=int(input())
arr=[int(input()) for idx in range(n)]

print(length(list(set(arr))))


### FIXED CODE ###

n=int(input())

radii=[int(input()) for _ in range(n)]
print(len(list(set(radii))))
import math
N=int(input())
frac=[]
result=len(str(N))
for i in range(1,math.ceil(math.sqrt(N))):
  if N%i==0:
    frac.append(len(str(int(N/i))))

print(min(frac))

### FIXED CODE ###

import math
N=int(input())
frac=[]
for i in range(1,math.floor(math.sqrt(N))+1):
  if N%i==0:
    frac.append(len(str(int(N/i))))
if N !=1:
  print(min(frac))
else:
  print(1)
n,c,k=map(int,input().split())
t=[int(input()) for _ in range(n)]+[10**9]
t.sort()
b=1
p=0
while p<n:
  l=t[p]+k
  pp=1
  f=1
  while pp<c and f:
    p+=1
    if t[p]<=l:
      pp+=1
      if pp==c:
        p+=1
    else:
      f=0
  if p<n:
    b+=1
print(b)

### FIXED CODE ###

n,c,k=map(int,input().split())
t=[int(input()) for _ in range(n)]+[10**10]
t.sort()
b=1
p=0
if c==1:
  print(n)
  exit()
while p<n:
  l=t[p]+k
  pp=1
  f=1
  while pp<c and f:
    p+=1
    if t[p]<=l:
      pp+=1
      if pp==c:
        p+=1
    else:
      f=0
  if p<n:
    b+=1
print(b)
import numpy as np
n = int(input())
a = np.array(input().split(),dtype=int)
ba = np.array(list(format(i,'b').zfill(60)) for i in a])
#print(ba)
mod = 10**9+7


#2^iをmodで割った余りを出しておく
twos = [1]
for i in range(1,60):
    twos.append((twos[i-1]*2)%mod)

#各baのbitごとに0の個数を求める
c0 = np.sum(ba, axis=1)


#答えは各bitごとの(0の数)*(1の数)より求まる
ans = 0
for i in range(60):
    ans += (((c0[59-i]*(n-c0[59-i]))%mod)*twos[i])%mod

ans %= mod
print(int(ans))


### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array(input().split(),dtype=int)
mod = 10**9+7

twos = 1
ans = 0
for i in range(0,60):
    cou1 = np.count_nonzero((a >> i) & 1)
    ans += (cou1*(n-cou1)*twos)%mod
    twos = (twos*2)%mod

ans %= mod
print(ans)
import collections
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A1 = collections.Counter(A)
B1 = collections.Counter(B)
A2 = A1.most_common()
B2 = B1.most_common()

for i in range(len(B2)):
  if A2[i][1] + B2[i][1] > N:
    print("No")
    quit()


B.reverse()    
s = 0
t = N - 1
for i in range(N):
  if A[i] == B[i]:
    if (A[s] != B[i]) and (A[i] != B[s]):
      x = B[s]
      B[s] = B[i]
      B[i] = x
      s += 1
    elif (A[t] != B[i]) and (A[i] != B[t]) :
      x = B[t]
      B[t] = B[i]
      B[i] = x
      t -= 1
    else:
      print("No")
      quit()
  
#print(B)  
print("Yes")  
for i in range(N):
  print(B[i], end = " ")
print("")

  
    


### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A1 = collections.Counter(A)
B1 = collections.Counter(B)
A2 = A1.most_common()
B2 = B1.most_common()

if A2[0][0] == B2[0][0]:
  if min(A2[0][1], B2[0][1]) > int(N / 2):
    print("No")
    quit()

B.reverse()    
s = 0
t = N - 1
for i in range(N):
  if A[i] == B[i]:
    if (A[s] != B[i]) and (A[i] != B[s]):
      x = B[s]
      B[s] = B[i]
      B[i] = x
      s += 1
    elif (A[t] != B[i]) and (A[i] != B[t]) :
      x = B[t]
      B[t] = B[i]
      B[i] = x
      t -= 1
    else:
      print("No")
      quit()
  
#print(B)  
print("Yes")  
for i in range(N):
  print(B[i], end = " ")
print("")
x, y = map(int, input().split())

for a in range(x + 1):
    if (2 * a + 4 * (x - a) == y) and (2 * x <= y <= 4 * x):
        print('Yes')
        exit(1)

print('No')

### FIXED CODE ###

x, y = map(int, input().split())

for a in range(x + 1):
    tem = 2 * a + 4 * (x - a)
    if (tem == y):
        #  and (2 * x <= y <= 4 * x):
        print('Yes')
        exit()

print('No')
midScore =[0]*50
finScore = [0]*50
reScore = [0]*50
personNum = 0
while True:
    m,f,r = map(int,input().split())
    midScore[personNum] = m
    finScore[personNum] = f
    reScore[personNum] = r
    personNum += 1
    if m is f is r is -1:
        break
    
    
for person in range(personNum):
    totalScore = midScore[person] + finScore[person]
    if midScore[person] is finScore[person] is reScore[person] is -1:
        pass
    elif midScore[person] == -1 or finScore[person] == -1:
        print("F")
    elif 80<=totalScore:
        print("A")
    elif 65<=totalScore<80:
        print("B")
    elif 50<=totalScore<65:
        print("C")
    elif 30<=totalScore<50:
        if 50<=reScore:
            print("C")
        else:
            print("D")
    elif totalScore<30:
        print("F")


### FIXED CODE ###

midScore =[0]*50
finScore = [0]*50
reScore = [0]*50
personNum = 0
while True:
    m,f,r = map(int,input().split())
    midScore[personNum] = m
    finScore[personNum] = f
    reScore[personNum] = r
    personNum += 1
    if m is f is r is -1:
        break
    
    
for person in range(personNum):
    totalScore = midScore[person] + finScore[person]
    if midScore[person] is finScore[person] is reScore[person] is -1:
        pass
    elif midScore[person] == -1 or finScore[person] == -1:
        print("F")
    elif 80<=totalScore:
        print("A")
    elif 65<=totalScore<80:
        print("B")
    elif 50<=totalScore<65:
        print("C")
    elif 30<=totalScore<50:
        if 50<=reScore[person]:
            print("C")
        else:
            print("D")
    elif totalScore<30:
        print("F")
s = sorted(list(str(input())))
t = sorted(list(str(input())), reverse = True)
x = 0
y = 0
for i in range(len(s)):
    if s[i] < t[i]:
        print('Yes')
        break
    if s[i] == t[i]:
        x += 1
    else:
        y += 1
if x == len(s) and len(s) < len(t):
    print('Yes') 
elif s == t:
    print('No')
elif y == len(s):
    print('No')

### FIXED CODE ###

import sys
s = sorted(list(str(input())))
t = sorted(list(str(input())), reverse = True)
u = min(len(s), len(t))
for i in range(min(len(s), len(t))):
    if s[i] < t[i]:
        print('Yes')
        sys.exit()
    if s[i] > t[i]:
        print('No')
        sys.exit()
if s[0:u] == t[0:u] and len(s) < len(t):
    print('Yes')
elif s[0:u] == t[0:u] and len(s) >= len(t):
    print('No')
N,R=input().split()
N=int(N)
R=int(R)
if N>=10:
	print(R)
else :
	prinAt((100*(10-N))+R)

### FIXED CODE ###

N,R=input().split()
N=int(N)
R=int(R)
if N>=10:
	print(R)
else :
	print((100*(10-N))+R)
import math 
A,B = map(float,input().split())

B = decimal(B)
print(int(A*B))

### FIXED CODE ###

from decimal import Decimal
a,b = map(str,input().split())
a = int(a)
b = Decimal(b)
print(int(a*b))
s = input()
K = int (input())


def sort_here(ll):  # バブルソート
    for m in range(len(ll)):
        for n in range(len(ll)-1-m):
            A, B = compare(ll[n], ll[n+1])
            ll[n] = A
            ll[n + 1] = B
    return ll


def compare_(A, B):
    # このゲームにおける比較
    # 小、大の順で返す
    a = len(A)
    b = len(B)

    if a > b:
        if A[:b] == B:
            return B, A
    elif b > a:
        if B[:a] == A:
            return A, B

    for i in range(len(min(A, B))):
        if A[i] > B[i]:
            return B, A
        elif A[i] < B[i]:
            return A, B

def compare(A, B):
    # このゲームにおける比較
    # 小、大の順で返す
    for i in range(len(min(A, B))):
        if A[i] > B[i]:
            return B, A
        elif A[i] < B[i]:
            return A, B

    if len(A) < len(B):
        return A, B
    elif len(B) < len(A):
        return B, A
    else:
        raise Exception


# まずはありうるsubstringを準備
i_list = []
for i in range(1, len(s) + 1):
    # i文字数のsutringをまずは作る
    for j in range(len(s) - i + 1):
        cand = s[j:j+i]
        if cand not in i_list:
            i_list.append(s[j:j+i])

#print(i_list)

# 並び替え
i_list = sort_here(i_list)
#print(i_list)


# 出力
print(i_list[K-1])








### FIXED CODE ###

# 整数の入力
a, b, c, d = list(map(int, input().split(" ")))

if abs(a-c) <= d:
    print("Yes")

else:
    if (abs(a-b) <= d) & (abs(b-c) <= d):
        print("Yes")
    else:
        print("No")
s = (int, input().split())
count = 0
for i in s if s==1:
	count+=1

### FIXED CODE ###

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

a,b,c = (int(x) for x in input())
list = [a, b, c]
count = 0
for i in list:
	if i == 1:
		count += 1
print(count)
N = int(input())
H = tuple(map(int, input(),split()))

dp = [0, abs(H[1]-H[0])]

if N > 2:
    for i in range(2, N):
        dp[i] = min(dp[i-2] + abs(H[i]-H[i-2]), dp[i-1] + abs(H[i]-H[i-1]))
else:
    print(dp[-1])
    exit()

print(dp[-1])


### FIXED CODE ###

N = int(input())
H = tuple(map(int, input().split()))

dp = [0] * N
dp[1] = abs(H[1]-H[0])
if N > 2:
    for i in range(2, N):
        dp[i] = min(dp[i-2] + abs(H[i]-H[i-2]), dp[i-1] + abs(H[i]-H[i-1]))
else:
    print(dp[-1])
    exit()

print(dp[-1])
a, b = map(int, input().split())
if a < b:
    print(f"{a}"*b)
elif a >= b:
    print(f"{b}"*a)

### FIXED CODE ###

a, b = map(str, input().split())
if int(a) < int(b):
    print("{}".format(a)*int(b))
else:
    print("{}".format(b)*int(a))
def divisor(A, B):
    if A==1:
        return A + B
    if B==1:
        return B-A
    if B % A == 0:
        return A + B
    return B - A
  
  A, B = map(int, input().split(" "))
  print(divisor(A, B))

### FIXED CODE ###

def divisor(A, B):
    if A==1:
        return A + B
    if B==1:
        return B-A
    if B % A == 0:
        return A + B
    return B - A

A, B = map(int, input().split(" "))
print(divisor(A, B))
import copy

n, q = map(int, input().split())
s = input()

cnt = [0]
for i in range(n):
    if s[i] == 'A' and s[i+1] == 'C':
        cnt.append(cnt[-1] + 1)
    else:
        cnt.append(cnt[-1])

for i in range(q):
    l, r = map(int, input().split())
    print(cnt[r-1] - cnt[l-1])

### FIXED CODE ###

import copy

n, q = map(int, input().split())
s = input()

cnt = [0]
for i in range(n-1):
    if s[i] == 'A' and s[i+1] == 'C':
        cnt.append(cnt[-1] + 1)
    else:
        cnt.append(cnt[-1])

for i in range(q):
    l, r = map(int, input().split())
    print(cnt[r-1] - cnt[l-1])
# ARC60 D recursive with memorization
dp = [{} for j in range(N+1)]
def rec_dp(i, j):
    if(j in dp[i]):
        return dp[i][j]
    
    res = 0
    if(i == N):
        res = 0
    elif(j < w[i]):
        res = rec_dp(i+1, j)
    else:
        res = max(rec_dp(i+1, j), rec_dp(i+1, j-w[i]) + v[i])
    
    dp[i][j] = res
    return res

print(rec_dp(0, w_limit))

### FIXED CODE ###

# ARC60 D input
nw = list(map(int, input().split()))
N = nw[0]
w_limit = nw[1]

w = []
v = []
for i in range(N):
    wv = list(map(int, input().split()))
    w.append(wv[0])
    v.append(wv[1])

# ARC60 D recursive with memorization
dp = [{} for j in range(N+1)]
def rec_dp(i, j):
    if(j in dp[i]):
        return dp[i][j]
    
    res = 0
    if(i == N):
        res = 0
    elif(j < w[i]):
        res = rec_dp(i+1, j)
    else:
        res = max(rec_dp(i+1, j), rec_dp(i+1, j-w[i]) + v[i])
    
    dp[i][j] = res
    return res

print(rec_dp(0, w_limit))
import copy


def dfs(array, pos, res_array):
    res = False
    if False not in res_array:
        return True
    elif res_array[pos]:
        return False
    else:
        res_array[pos] = True
        for i in array[pos]:
            if dfs(array, i, res_array):
                res = True
    return res


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

array = [[int(x) for x in input().split()] for x in range(m)]
res_array = [True] + [False for x in range(n)]

res = 0
for i in range(len(array)):
    adj_array = [[] for x in range(n + 1)]
    tmp_array = array[:i] + [[]] + array[i+1:]
    for item in tmp_array:
        if len(item) == 0:
            continue
        adj_array[item[0]].append(item[1])
        adj_array[item[1]].append(item[0])
    res += 1 ^ dfs(adj_array, -i-1, copy.copy(res_array))

print(res)


### FIXED CODE ###

def dfs(array, visited, next):
    if visited[next] is not True and len(array[next]) != 0:
        visited[next] = True
        for next_node in array[next]:
            visited = dfs(array, visited, next_node)
    else:
        return visited
    return visited


n, m = map(int, input().split())
edge_array = []
for i in range(m):
    edge_array.append([int(x) for x in input().split()])

cnt = 0
for _ in edge_array:
    remove_edge = edge_array[0]
    edge_array.remove(remove_edge)
    node_array = [[] for x in range(n + 1)]
    # 隣接リストの作成
    for edge in edge_array:
        node_array[edge[0]].append(edge[1])
        node_array[edge[1]].append(edge[0])
        visited = [False]*(n+1)
    res = dfs(node_array, visited, 1)
    if res.count(False) != 1:
        cnt += 1
    edge_array.append(remove_edge)

print(cnt)
#!/usr/bin/env python

n=int(raw_input().strip())
arr=map(int,raw_input().split())

b=0
cnt=0

for i in xrange(n-1):
    diff=arr[i+1]-arr[i]
    if b*diff<0:
        cnt+=1
        b=0
    elif d==0:
        b=diff
print cnt+1

### FIXED CODE ###

#!/usr/bin/env python

n=int(raw_input().strip())
arr=map(int,raw_input().split())

b=0
cnt=0

for i in xrange(n-1):
    diff=arr[i+1]-arr[i]
    if b*diff<0:
        cnt+=1
        b=0
    elif b==0:
        b=diff
print cnt+1