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

N = int(input())
A = [int(i) for i in input().split()]

Y = [0] * N

pattern = A[0] + 1

for i in range(pattern):
    Y[0] = i * 2
    # print("pattern", Y[0])
    for k in range(1, N):
        # print("k", k)
        Y[k] = 2 * A[k - 1] - Y[k - 1]
        # print("Y:", Y[k])
        if Y[k] < 0:
            break
        if k == N - 1 and (Y[k] + Y[0]) / 2 == A[k]:
            ans = ' '.join([str(n) for n in Y])
            print(ans)
            exit()

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]

Y = [0] * N
s = 0
for i in range(N):
    if i % 2 == 0:
        s += A[i]
    else:
        s -= A[i]

Y[0] = s
for i in range(1, N):
    Y[i] = 2 * A[i - 1] - Y[i - 1]

ans = ' '.join([str(n) for n in Y])
print(ans)
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, shortest_path
n, m, *AB = map(int, open(0).read().split())
graph = [[10**9]*n for _ in range(n)]
for a, b in zip(AB[::2], AB[1::2]):
    graph[a-1][b-1] = graph[b-1][a-1] = 1
G = csgraph_from_dense(graph, null_value=10**9)
d, p = shortest_path(G, indices=0, method='D', return_predecessors=1)
print('Yes')
print(*map(lambda x: int(x)+1, p[1:]), sep='\n')

### FIXED CODE ###

from collections import deque
n, m, *AB = map(int, open(0).read().split())
graph = [[] for _ in range(n)]
for a, b in zip(AB[::2], AB[1::2]):
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

d = [0] * n
queue = deque([0])
while queue:
    current_node = queue.popleft()
    for next_node in graph[current_node]:
        if d[next_node] == 0:
            d[next_node] = current_node+1
            queue.append(next_node)
print('Yes')
print(*d[1:], sep='\n')
### BUGGY CODE ###

import sys

N, M = map(int, input().split())
ship_list = list()
way_list = list()
for i in range(M):
    a, b = map(int, input().split())
    ship_list.append((a, b))
    if b == N:
        way_list.append(a)

for dest in ship_list:
    if dest[1] in way_list and dest[0] == 1:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")

### FIXED CODE ###

import sys

def possible():
    print("POSSIBLE")
    sys.exit()

def main():
    N, M = map(int, input().split())
    hashdict = dict()
    for i in range(1009):
        hashdict[i] = list()
    alist = list()
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            temp = b % 1009
            hashdict[temp].append(b)
        if b == N:
            alist.append(a)

    for start in alist:
        temp = start % 1009
        if start in hashdict[temp]:
            possible()
    print("IMPOSSIBLE")

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

def compute_cost(point_candles):
    if(point_candles[0] * point_candles[-1] >= 0):
        return max(abs(point_candles[0]), abs(point_candles[-1]))
    else:
        return point_candles[-1] - point_candles[0] + min(abs(point_candles[0]), abs(point_candles[-1])) 

N, K = list(map(int, input().strip().split(" ")))
candles = list(map(int, input().strip().split(" ")))

patterns = N - K + 1

min_cost = None

for start_index in range(patterns):
    cost = compute_cost(candles[start_index:start_index + K])
    if(min_cost == None or min_cost > cost):
        min_cost = cost
print(min_cost)

### FIXED CODE ###

N, K = list(map(int, input().strip().split(" ")))
candles = input().strip()
min_cost_index = candles.count("-")
candles = list(map(int, candles.split(" ")))

def update():
    start_index = max(0, min_cost_index - K - 1)
    end_index = min(N, min_cost_index + K + 1)
    new_candles = candles[start_index: end_index]
    return new_candles

def compute_cost(start_index):
    start_point = candles[start_index]
    end_point = candles[start_index + K - 1]
    if(start_point * end_point >= 0):
        return max(abs(start_point), abs(end_point))
    else:
        return end_point - start_point + min(-start_point, end_point) 

candles = update()

N = len(candles)
min_cost = compute_cost(0)
patterns = N - K + 1

for start_index in range(patterns):
    cost = compute_cost(start_index)
    if(min_cost > cost):
        min_cost = cost
print(min_cost)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = list(input())
for _ in range(Q):
    ans = 0
    l, r = map(int, input().split())
    tar = S[l-1:r]
    length = r - l + 1
    for i in range(length - 1):
        if tar[i] == 'A':
            if tar[i + 1] == 'C':
                ans += 1
    print(ans)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
imosu = [0] * (N + 1)
for i in range(N):
    imosu[i + 1] = imosu[i] + (1 if S[i:i+2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(imosu[r-1]-imosu[l-1])
### BUGGY CODE ###

import bisect
n, m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
total = sum(a)
cnt = 0
for i in range(m):
    b, c = map(int,input().split())
    bi = bisect.bisect(a, c)
    mb = min(bi, b)
    a += [c]*mb
    total += mb * c
    cnt += mb
a.sort()
print(total - sum(a[:cnt]))

### FIXED CODE ###

n, m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
bc = [list(map(int,input().split())) for _ in range(m)]
bc.sort(key=lambda x:x[1], reverse=True)

ad = 0
idx = 0
for b, c in bc:
    for i in range(min(b, n-idx)):
        if a[idx+i] < c:
            continue
        else:
            ad += c*i
            idx += i
            print(ad + sum(a[idx:]))
            exit()
    ad += c*min(b, n-idx)
    idx += min(b, n-idx)
print(ad + sum(a[idx:]))
### BUGGY CODE ###

import math

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

while True:
    if abs(N-K) < N:
        N = abs(N-K)
        continue
    else:break

print(N)


### FIXED CODE ###

import math

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

while True:
    if N>K:
      N = abs(N%K)
    if abs(N-K) < N:
        N = abs(N-K)
        continue
    else:break

print(N)
### BUGGY CODE ###

N, M, R = map(int, input().split())
r = list(map(lambda x:int(x) - 1, input().split()))

dist = [[float('inf')] * N for _ in range(N)]
for _ in range(M):
	tmp = list(map(int, input().split()))
	dist[tmp[0] - 1][tmp[1] - 1] = dist[tmp[1] - 1][tmp[0] - 1] = tmp[2]

for k in range(N):
	for i in range(N):
		for j in range(N):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

ans = float('inf')
seen = []
def DFS():
	global ans
	for i in range(len(r)):
		if i not in seen:
			seen.append(i)
			if len(seen) == len(r):
				sumDist = 0
				for j in range(len(seen) - 1):
					sumDist += dist[r[seen[j]]][r[seen[j+1]]]
				ans = min(ans, sumDist)
			else:
				DFS()
			del seen[-1]

DFS()
print(ans)

### FIXED CODE ###

import itertools
 
N, M, R = map(int, input().split())
r = [int(x) - 1 for x in input().split()]
 
dist = [[float('inf')] * N for _ in range(N)]
for _ in range(M):
	a, b, c = map(int, input().split())
	a -= 1
	b -= 1
	dist[a][b] = dist[b][a] = c
 
for k in range(N):
	for i in range(N):
		for j in range(N):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
 
ans = float('inf')
k = list(itertools.permutations(r))
for i in k:
	sumDist = 0
	for j in range(len(i) - 1):
		sumDist += dist[i[j]][i[j+1]]
	ans = min(ans, sumDist)
print(ans)
### BUGGY CODE ###

def main():
    from scipy.sparse.csgraph import dijkstra
    n = int(input())
    G = [[float('inf') for i in range(n)] for i in range(n)]
    for _ in range(n-1):
        a,b,c = map(int,input().split())
        G[a-1][b-1] = G[b-1][a-1] = c
    q,k = map(int,input().split())
    d = dijkstra(G)[k-1]
    for _ in range(q):
        x,y = map(int,input().split())
        print(int(d[x-1]+d[y-1]))

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    G = {}
    for i in range(n):
        G[i+1] = []
    for _ in range(n-1):
        a,b,c = map(int,input().split())
        G[a] += [[b,c]]
        G[b] += [[a,c]]
    q,k = map(int,input().split())
    dist = [-1]*n
    dist[k-1] = 0
    que = [k]
    while len(que) > 0:
        s = que.pop(0)
        for [nv,c] in G[s]:
            if dist[nv-1] != -1:
                continue
            dist[nv-1] = dist[s-1]+c
            que.append(nv)
    for _ in range(q):
        x,y = map(int,input().split())
        print(dist[x-1]+dist[y-1])

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

N,Q = map(int, input().split())
abL = [[int(x) for x in input().split()] for _ in range(N-1)]
tree = [[0]*(N+1) for _ in range(N+1)]
graph = [[] for _ in range(N+1)]
for a,b in abL:
    graph[a].append(b)

for a in range(N, 0, -1):
    incL = graph[a]
    for b in incL:
        for i in range(a):
            if a in graph[i]:
                graph[i].append(b)
    graph[a].append(a)

pxL = [[int(x) for x in input().split()] for _ in range(Q)]

for p,x in pxL:
    tmpL = graph[p]
    for b in tmpL:
        tree[p][b] += x

for i in range(1, N+1):
    sum_ = 0
    for j in range(1, N+1):
        sum_ += tree[j][i]
    print(sum_, end=" ")


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

N,Q = map(int, input().split())
graph = [[] for _ in range(N)]
counter = [0]*N
for i in range(N-1):
    a,b = map(int, input().split()) 
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

for i in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x

def dfs(v, parent):
    for i in graph[v]:
        if i==parent:
            continue
        counter[i] += counter[v]
        dfs(i, v)
        
dfs(0, -1)
print(*counter)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, Q = mapint()
Cs = list(mapint())

#####segfunc######
def segfunc(x,y):
    return x.union(y)

def init(init_val):
    for i in range(N):
        seg[i+num-1]=init_val[i]    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1], seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

num =2**(N-1).bit_length()
ide_ele = set()
seg=[ide_ele]*2*num
init([set([c]) for c in Cs])
for _ in range(Q):
    l, r = mapint()
    print(len(query(l-1, r)))

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, Q = mapint()
Cs = list(mapint())
LR = []
for i in range(Q):
    l, r = mapint()
    LR.append((l, r, i))
LR.sort(key=lambda x:x[1])
A = [0]*N

def add(A,a,w):#リストに値を追加する関数
    x = a
    while x <= N:
        A[x-1] += w
        x += x&(-x)

def sums(A,a):#k番目までの和
    x = a
    S = 0
    while x != 0:
        S += A[x-1]
        x -= x&(-x)
    return S

ans = [0]*Q
idx = 0
dic = {}
for i in range(N):
    c = Cs[i]
    if c not in dic:
        dic[c] = i+1
        add(A, i+1, 1)
    else:
        past = dic[c]
        dic[c] = i+1
        add(A, past, -1)
        add(A, i+1, 1)
    while idx<Q and LR[idx][1]<=i+1:
        l, r, ans_idx = LR[idx]
        ans[ans_idx] = sums(A, r)-sums(A, l-1)
        idx += 1
for a in ans:
    print(a)
### BUGGY CODE ###

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

L = [[0 for _ in range(w)] for _ in range(h)]
R = [[0 for _ in range(w)] for _ in range(h)]
U = [[0 for _ in range(w)] for _ in range(h)]
D = [[0 for _ in range(w)] for _ in range(h)]

def make(L, R, U, D):
    for i in range(h):
        for j in range(w):
            if s[i][j] == '#':
                L[i][j] == 0
            elif s[i][j] == '.':
                if j == 0:
                    L[i][j] = 1
                else:
                    L[i][j] = L[i][j-1] + 1

            ri = i
            rj = w-j-1
            if s[ri][rj] == '#':
                R[ri][rj] == 0
            elif s[ri][rj] == '.':
                if rj == w-1:
                    R[ri][rj] = 1
                else:
                    R[ri][rj] = R[ri][rj+1] + 1
        

            if s[i][j] == '#':
                D[i][j] == 0
            elif s[i][j] == '.':
                if i == 0:
                    D[i][j] = 1
                else:
                    D[i][j] = D[i-1][j] + 1

            ui = h-i-1
            uj = j
            if s[ui][uj] == '#':
                U[ui][uj] == 0
            elif s[ui][uj] == '.':
                if ui == h-1:
                    U[ui][uj] = 1
                else:
                    U[ui][uj] = U[ui+1][uj] + 1
    
'''
    for j in range(w):
        for i in range(h):
            if s[i][j] == '#':
                D[i][j] == 0
            elif s[i][j] == '.':
                if i == 0:
                    D[i][j] = 1
                else:
                    D[i][j] = D[i-1][j] + 1

            ui = h-i-1
            uj = j
            if s[ui][uj] == '#':
                U[ui][uj] == 0
            elif s[ui][uj] == '.':
                if ui == h-1:
                    U[ui][uj] = 1
                else:
                    U[ui][uj] = U[ui+1][uj] + 1
'''


def right(i, j):
    ui = i-1
    di = i+1
    lj = j-1
    rj = j+1
    cnt = 1

    while ui >= 0 and s[ui][j] != '#':
        ui -= 1 
        cnt += 1

    while di < h and s[di][j] != '#':
        di += 1 
        cnt += 1

    while lj >= 0 and s[i][lj] != '#':
        lj -= 1 
        cnt += 1

    while rj < w and s[i][rj] != '#':
        rj += 1 
        cnt += 1
    #print(i, j, ui, di, lj, rj, cnt)
    return cnt

make(L, R, U, D)

ans = 0
#print(L)
#print(R)
#print(U)
#print(D)

for i in range(h):
    for j in range(w):
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)

print(ans)

### FIXED CODE ###

import numpy as np

h, w = map(int, input().split())
s = np.array([list(input()) for _ in range(h)]) == '.'

L = np.zeros((h, w), dtype=int)
R = np.zeros((h, w), dtype=int)
U = np.zeros((h, w), dtype=int)
D = np.zeros((h, w), dtype=int)

for i in range(h):
    D[i] = (D[i-1]+1) * s[i]
    U[-i-1] = (U[-i]+1) * s[-i-1]

for i in range(w):
    R[:, i] = (R[:, i-1]+1) * s[:, i]
    L[:, -i-1] = (L[:, -i]+1) * s[:, -i-1]


print(np.max(D+U+R+L)-3)
### BUGGY CODE ###

import itertools
while 1:
	n = input()
	if n == 0: break
	s = sorted(map(int,raw_input().split()))
	sm = ans = sum(s)
	for i in range(1,n/2+1):
		for party in itertools.combinations(s,i):
			cur = sm - 2*sum(party)
			ans = min(ans,abs(cur))
	print ans

### FIXED CODE ###

def S(i,x,y):
	if 2*x >= A: return 2*x-A
	if 2*y >= A: return 2*y-A
	return min(S(i+1,x+a[i],y),S(i+1,x,y+a[i]))
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))[::-1]
	A = sum(a)
	print S(1,a[0],0)
### BUGGY CODE ###

X = input()

for i in range (0, 100001):
	X = X.replace("ST", '')

print(len(X))

### FIXED CODE ###

X = str(input())

Tn = 0
Sn = 0
Nagasa = len(X)

for i in range (0, Nagasa):
	if X[i] == 'T':
		if Sn == 0:
			Tn+=1
		else:
			Sn-=1
	else:
		Sn+=1

print(2*Tn)
### BUGGY CODE ###

import math
N,M=map(int,input().split())
a=[]
for i in range(M):
    tmp=list(map(int,input().split()))
    tmpc=list(map(int,input().split()))
    c=0
    for j in range(len(tmpc)):
        c+=2**(tmpc[j]-1)
    tmp[1]=c
    a+=[tmp]


dp=[[10**10 for j in range(2**N)] for i in range(M)]
dp[0][0]=0
dp[0][a[0][1]]=a[0][0]


for i in range(1,M):
    dp[i]=dp[i-1]
    for j in range(2**N):
        z,p=a[i][0],a[i][1]
        q=j|p
        dp[i][q]=min(dp[i-1][j]+z,dp[i][q])

ans=dp[M-1][2**N-1]
print(ans if ans<10**10 else -1)

### FIXED CODE ###

def main():
    N,M=map(int,input().split())
    L=2**N
    dp=[10**10 for i in range(L)]
    dp[0]=0


    for i in range(M):
        a, _ = map(int, input().split())
        key=sum([2**(int(i)-1) for i in input().split()])
        for j in range(L):
                q=j|key
                dp[q]=min(dp[j]+a,dp[q])


    ans=dp[L-1]
    print(ans if ans<10**10 else -1)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

n, m = map(int, input().split())
gate = []
l, r = map(int, input().split())
ID = {i for i in range(l, r + 1)}
for i in range(1, m):
    l, r = map(int, input().split())
    gate = {j for j in range(l, r + 1)}
    ID = ID & gate
print(len(ID))

### FIXED CODE ###

n, m = map(int, input().split())
gate = []
l, r = map(int, input().split())
for i in range(1, m):
    m, s = map(int, input().split())
    if l < m:
        l = m
    if s < r:
        r = s
print(len([i for i in range(l, r + 1)]))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
a, b= map(int, input().split())

t = [a,b]

r = 0
t_r = []
for i in range(int(10**6/2)):

    l = [i, i*2]

    if l[0] > t[0] or  l[1] > t[1]:
        break

    for j in range(int(10**6/2)):

        l2 = [i + j*2, i*2 + j]
        if l2[0] > t[0] or  l2[1] > t[1]:
            break

        if l2 == t:
            t_r.append([i,j])
            break



for l in t_r:
    r += l[0] + l[1]
print(r)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import math

def mod_factorial(n):
    mod = 10**9+7

    if n < 1:
        return 1

    r = n
    for i in range(n-1):
        r = r*(i+1) % mod
    
    return r

def mod_pow(n,m):

    mod = 10**9+7
    r = 1

    while m > 0:
        if m & 1:
            r = r*n % mod
        n = n * n % mod
        m = m>>1

    return(r)



def mod_comb(n, k):
    mod = 10**9+7

    if n+k < 1:
        return 1
    
    a = mod_factorial(n)
    b = mod_pow(mod_factorial(k), mod-2)
    c = mod_pow(mod_factorial(n-k), mod-2)


    return (a * ((b * c) % mod)) % mod


a, b= map(int, input().split())

t = [a,b]

r = 0
mod = 10**9+7

x = (2*a-b)
y = (2*b-a)

if x%3 == 0 and y%3 == 0 and x*y >=0:
    m = int(x/3)
    n = int(y/3)

    r += mod_comb(n+m,m)

print(r)
### BUGGY CODE ###

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

t = [0]*N
d = [0]*N
for i in range(N):
    t[i], d[i] = map(int, input().split())
ans = int(0)
s = max(t)
value = [0]*s
kind = int(0)
k = []

top = [0]*s
all = []
delcan = []
pairs = zip(t,d)

all = sorted(pairs, key=lambda x: x[1],reverse=True)
for i in range(K):
    value[0] += all[i][1]
    if not all[i][0] in k:
        k.append(all[i][0])
        kind += 1
    else:
        delcan.append(all[i][1])

for i in range(N):
    if top[t[i]-1]<d[i]:
        top[t[i]-1] = d[i]

for i in k:
    top[i-1] = 0
while 0 in top:
    top.remove(0)
top.sort(reverse=True)
delcan.sort()

value[0] += kind**2
ans = value[0]
for i in range(min(len(top),len(delcan))):
    if top and delcan:
        value[i+1] = value[i] - delcan[i] + top[i] + (kind * 2 + 1)
    kind +=1
    if ans<value[i+1]:
        ans = value[i+1]
print(ans)

### FIXED CODE ###

def examA():
    L = LI(); L.sort()
    ans = L[0]*L[1]//2
    print(ans)
    return

def examB():
    def fun(s):
        if s%2==0:
            return s//2
        else:
            return s*3+1
    S = I()
    d = defaultdict(bool)
    d[S] = True; cur = 1
    while(True):
        cur +=1
        S = fun(S)
        if d[S]:
            break
        d[S] = True
    print(cur)
    return

def examC():
    N = I()
    H = LI()
    cur = 0
    ans =0
    for i in range(N):
        if cur<H[i]:
            ans += H[i]-cur
        cur = H[i]
    print(ans)
    return

def examD():
    N, K = LI()
    TS = [LI() for _ in range(N)]
    choice = []
    keep = []
    d = defaultdict(int)
    TS.sort(key=lambda x:x[1],reverse=True)
    for i,(t,s) in enumerate(TS):
        if d[t]==0:
            if i < K:
                d[t] = -1
                choice.append(s)
            else:
                d[t] = s
        else:
            if i<K:
                keep.append(s)
    keep.sort()
    D = sorted(d.values(),reverse=True)
#    print(choice); print(keep); print(D)
    cur = len(choice)
    now = cur**2 +sum(choice)+sum(keep)
    ans = copy.deepcopy(now)
    for i,k in enumerate(keep):
        if D[i]<0:
            break
        now += ((cur+i)*2+1) + (D[i]-k)
        ans = max(ans,now)
#        print(now)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,ALPHABET, _ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 1e-9
alphabet = [chr(ord('a') + i) for i in range(26)]
ALPHABET = [chr(ord('A') + i) for i in range(26)]

if __name__ == '__main__':
    examD()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np

def chmax(a, b):
  if a<b:
    a = b
  return a

weight = np.array([0]*110)
value = np.array([0]*110)
dp = np.array([[0]*100010 for i in range(110)])

N, W = map(int, input().split())
for i in range(N):
  weight[i], value[i] = map(int, input().split())

# dp roop
for i in range(N):
  sum_w = 0
  while sum_w <= W:
    if (sum_w - weight[i]) >= 0:
      dp[i+1][sum_w] = chmax(dp[i+1][sum_w],
                             dp[i][sum_w - weight[i]] + value[i])
    dp[i+1][sum_w] = chmax(dp[i+1][sum_w], dp[i][sum_w])
    sum_w += 1
print(dp[N][W])    

### FIXED CODE ###

import sys
input = sys.stdin.readline

weight = [0]*110
value = [0]*110
dp = [[0]*100010 for i in range(110)]

N, W = map(int, input().split())
for i in range(N):
  weight[i], value[i] = map(int, input().split())

# dp roop
for i in range(N):
  sum_w = 0
  while sum_w <= W:
    if sum_w >= weight[i]:
      dp[i+1][sum_w] = max(dp[i][sum_w - weight[i]] + value[i], dp[i][sum_w])
    else:
      dp[i+1][sum_w] = dp[i][sum_w]
    sum_w += 1
print(dp[N][W])
### BUGGY CODE ###

S = str(input())
T = str(input())

s_box = []
t_box = []

for i in range(len(S)):
    if i >= len(S):
        break
    s_box.append(S.count(S[i]))
    t_box.append(T.count(T[i]))
    if s_box[i] == t_box[i]:
        S.replace(S[i], "")
        T.replace(T[i], "")
        continue
    else:
        print('No')
        exit()
print('Yes')

### FIXED CODE ###

#ABC110 C String Transformation

S = input()
T = input()

StoT = {}
TtoS = {}

for s, t in zip(S, T):
    if s in StoT.keys():
        if StoT[s] != t:
            print('No')
            exit()
    elif t in TtoS.keys():
        if TtoS[t] != s:
            print('No')
            exit()
    else:
        StoT[s] = t
        TtoS[t] = s
        
print('Yes')
### BUGGY CODE ###

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

count = 0
for i in range(N):
  lis = P_lis[0:i+1]
  lis = np.sign(lis - lis[i])
  if -1 in np.sign(lis[:-1]):
    count += 1
print(N-count)

### FIXED CODE ###

N = int(input())
P_lis = list(map(int, input().split()))
 
dummy = 2*10**5
answer = 0
 
for p in P_lis:
  if p <= dummy:
    answer += 1
    dummy = p
print(answer)