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

N,M = raw_input().split()
N,M = int(N),int(M)

pair = 0
c_pair = 0

while(0<N and 1<M):
    N -= 1
    M -= 2
    pair +=1

if (M!=0):
    c_pair = M / 4

print pair + c_pair


### FIXED CODE ###

s,c = map(int,raw_input().split())

if(s < c/2):
    s_pair = s
    c_pair = (c - s*2)/4
else:
    s_pair = c/2
    c_pair = 0

print s_pair + c_pair
### BUGGY CODE ###

S = input()
Q = int(input())
L = [list(map(str,input().split())) for i in range(Q)]

cnt = 0

for i in range(Q):
    if len(L[i]) == 1:
        cnt += 1
    else:
        if (int(L[i][1])+cnt)%2 == 0:
            S = S+L[i][2]
        else:
            S = L[i][2]+S

if cnt%2 == 0:
    print(S)
else:
    new_S = ''.join(list(reversed(S)))
    print(new_S)

### FIXED CODE ###

S = input()
Q = int(input())
L = [list(map(str,input().split())) for i in range(Q)]

cnt = 0
FR = ""
BA = ""

for i in range(Q):
    if len(L[i]) == 1:
        cnt += 1
    else:
        if (int(L[i][1])+cnt)%2 == 0:
            BA = BA + L[i][2]
        else:
            FR = L[i][2]+FR

if cnt%2 == 0:
    print(FR+S+BA)
else:
    new_S = ''.join(list(reversed(FR+S+BA)))
    print(new_S)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = [0, 0] + [int(input()) for _ in range(N - 1)]

child = [[] for _ in range(N + 1)]
for i, a in enumerate(A):
    child[a].append(i)

def depth(i):
    if not child[i]:
        return 0

    childDepth = [depth(to) for to in child[i]]
    childDepth.sort(reverse=True)
    ret = 0
    for j, d in enumerate(childDepth, start=1):
        ret = max(j + d, ret)
    return ret

ans = depth(1)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = [0, 0] + [int(input()) for _ in range(N - 1)]

child = [[] for _ in range(N + 1)]
for i, a in enumerate(A):
    child[a].append(i)

def depth(i):
    if not child[i]:
        return 0

    childDepth = [depth(to) for to in child[i]]
    childDepth.sort(reverse=True)
    ret = 0
    for j, d in enumerate(childDepth, start=1):
        ret = max(j + d, ret)
    return ret

ans = depth(1)
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
ans = []
ans.append(S)
T = [0,0,""]
for i in range(Q):
  TS = input()
  if TS == "1":
    ans.append(ans[0][::-1])
    ans.pop(0)
  else:
    T = TS.rstrip().split(" ")
    if int(T[1]) == 1:
      ans.append(T[2] + ans[0])
      ans.pop(0)
    else:
      ans.append(ans[0] + T[2])
      ans.pop(0)
print(ans[0])

### FIXED CODE ###

S = list(input())
mae = []
ato = []
rev = False
Q = int(input())
for i in range(Q):
    A = list(input().rstrip().split(" "))
    if int(A[0]) == 1:
        if rev:
            rev = False
        else:
            rev = True
    else:
        if (rev and int(A[1]) == 2 or not rev and int(A[1]) == 1):
            mae.append(A[2])
        else:
            ato.append(A[2])
if rev:
    ato.reverse()
    S.reverse()
    print("".join(ato) + "".join(S) + "".join(mae))
else:
    mae.reverse()
    print("".join(mae) + "".join(S) + "".join(ato))
### BUGGY CODE ###

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

a = sorted(a)

for i in range(q):
    
    for j in range(len(a)):
        if a[j] == bc[i][0]:
            a[j] = bc[i][1]
        # print(a)
    
    print(sum(a))

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
q = int(input())
bc = [list(map(int, input().split())) for _ in range(q)]

cnt = [0 for i in range(0, 10**5 + 1)]
for i in a:
    cnt[i] += 1

total = sum(a)

for j in range(q):
    b = bc[j][0]
    c = bc[j][1]
    cnt[c] += cnt[b]
    total += (c-b)*cnt[b]
    cnt[b] = 0
    print(total)
### BUGGY CODE ###

import itertools
import math

def func(x,y,z):
    return x**2+y**2+z**2+x*y+y*z+z*x
 
n = int(input())
s = int(math.sqrt(n))
nums = list(range(1,s))
arr = []
com = list(itertools.product(nums, repeat=3))
for i in range(len(com)):
    # print(com)
    ans = func(com[i][0],com[i][1],com[i][2])
    arr.append(ans)
 
for i in range(n):
    print(arr.count(i+1))

### FIXED CODE ###

import itertools
import math
import collections
def main():
    n = int(input())
    s = int(math.sqrt(n))
    a = list(itertools.product(range(1,s),repeat=3))
    ans = []
    for i in range(len(a)):
        t = a[i][0] ** 2 + a[i][1] ** 2 + a[i][2] ** 2 + a[i][0] * a[i][1] + a[i][1] * a[i][2] + a[i][2] * a[i][0]
        ans.append(t)
        # print(ans)
    c = collections.Counter(ans)
    for i in range(1,n+1):
        print(c[i])
        
        
main()
### BUGGY CODE ###

import numpy as np
S = input()
mod = 10 ** 9 + 7

n = len(S)
dp = np.zeros((n, 13), int)
a = S[-1]
x_ = dp[0]
l = [1, 10, 9, 12, 3, 4]
l = [[i * l_ % 13 for i in range(1, 10)] for l_ in l]
li = 1
if a == "?":
    x_[0:10] = 1
else:
    x_[int(a)] = 1
for i in range(1, n):
    x = dp[i]
    s = S[-i - 1]
    if s == "?":
        x += x_
        for v in l[li]:
            x[v:] += x_[:-v]
            x[:v] += x_[-v:]
    else:
        if s == "0":
            x += x_
        else:
            v = l[li][int(s) - 1]
            x[v:] += x_[:-v]
            x[:v] += x_[-v:]
    x %= mod
    li += 1
    li %= 6
    x_ = x
print(dp[-1][5])

### FIXED CODE ###

#!python3

LI = lambda: list(map(int, input().split()))

# input
S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    l1 = [0] * 13
    l1[0] = 1
    for i in range(1, n + 1):
        l2 = [0] * 13
        for j in range(10):
            x = w[i - 1] * j % 13
            for k in range(13):
                t = (x + k) % 13
                l2[t] += l1[k]
        l1 = [y % MOD for y in l2]
    
    ans = l1[m]
    print(ans)


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

n = int(input())

from fractions import Fraction

for i in range(1,3501):
    for j in range(1,3501):
        k = Fraction(4, n) - Fraction(1, i) - Fraction(1, j)
        if k.numerator == 1:
            print(i, j, k.denominator)
            import sys
            sys.exit()


### FIXED CODE ###

n = int(input())

from fractions import Fraction

for i in range(1,3501):
    for j in range(1,3501):
        if 4*i*j - n*i - n*j > 0:
            if (i * j * n) % (4*i*j - n*i - n*j) == 0 and (i * j * n) // (4*i*j - n*i - n*j) > 0:
                print(i,j, (i * j * n) // (4*i*j - n*i - n*j))
                import sys
                sys.exit()
### BUGGY CODE ###

N,K = map(int, input().split())
stone = []
for it in input().split():
    stone.append(int(it))
import sys
cost = [sys.maxsize]*len(stone)
cost[-1]=0
for i in range(len(stone)-1, 0, -1):
    h_now = stone[i]
    cost_now = cost[i]
    
    # one jump
    for jump in range(1,K+1):
        target = i - jump
        if target < 0:
            continue
        tmp_cost = abs(stone[i] - stone[target])+cost[i]
        if cost[target] > tmp_cost:
            cost[target] = tmp_cost

print(cost[0])

### FIXED CODE ###

N,K = map(int, input().split())
stone = []
for it in input().split():
    stone.append(int(it))
import sys
cost = [sys.maxsize]*len(stone)
cost[-1]=0
for i in range(len(stone)-1, 0, -1):
    h_now = stone[i]
    cost_now = cost[i]
    
    # one jump
    for jump in range(1,K+1):
        target = i - jump
        if target < 0:
            continue
        tmp_cost = abs(stone[i] - stone[target])+cost[i]
        if cost[target] > tmp_cost:
            cost[target] = tmp_cost

print(cost[0])
### BUGGY CODE ###

from itertools import product
from bisect import bisect_left
N,Ma,Mb = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
if N==1:
    if A[0][0]*Mb==A[0][1]*Ma:
        print(A[0][2])
    else:
        print(-1)
else:
    A1 = A[:N//2]  # N//2
    A2 = A[N//2:]  # N-N//2
    B1 = []
    for x in product((0,1),repeat=N//2):
        cnt1 = 0
        cnt2 = 0
        for i in range(N//2):
            cnt1 += x[i]*(Ma*A1[i][1]-Mb*A1[i][0])
            cnt2 += x[i]*A1[i][2]
        B1.append((cnt1,cnt2))
    B2 = []
    for x in product((0,1),repeat=N-N//2):
        cnt1 = 0
        cnt2 = 0
        for i in range(N-N//2):
            cnt1 += x[i]*(Ma*A2[i][1]-Mb*A2[i][0])
            cnt2 += x[i]*A2[i][2]
        B2.append((cnt1,cnt2))
    B1 = sorted(B1,key=lambda x:x[1])
    B1 = sorted(B1,key=lambda x:x[0])
    B2 = sorted(B2,key=lambda x:x[1])
    B2 = sorted(B2,key=lambda x:x[0])
    cmin = 10000
    for b1 in B1:
        b,c = b1[0],b1[1]
        if c==0:
            ind = bisect_left(B2,(-b,1))
        else:
            ind = bisect_left(B2,(-b,0))
        if ind<len(B2) and B2[ind][0]==-b:
            cmin = min(cmin,c+B2[ind][1])
    if cmin>=10000:
        print(-1)
    else:
        print(cmin)

### FIXED CODE ###

INFTY = 10**4
N,Ma,Mb = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
dp = [[[INFTY for _ in range(401)] for _ in range(401)] for _ in range(N+1)]
dp[0][0][0] = 0
for i in range(1,N+1):
    for j in range(401):
        for k in range(401):
            dp[i][j][k] = dp[i-1][j][k]
            a = A[i-1][0]
            b = A[i-1][1]
            c = A[i-1][2]
            if j>=a and k>=b:
                dp[i][j][k] = min(dp[i][j][k],dp[i-1][j-a][k-b]+c)
cmin = INFTY
for j in range(1,401):
    for k in range(1,401):
        if j*Mb==k*Ma:
            cmin = min(cmin,dp[N][j][k])
if cmin>=INFTY:
    print(-1)
else:
    print(cmin)
### BUGGY CODE ###

from sys import stdin
def stdinput():
    return stdin.readline().strip()

def main():
    altitutes = [0]
    for s in stdinput():
        if s == '\\':
            altitutes.append(altitutes[-1] - 1)
        elif s == '_':
            altitutes.append(altitutes[-1])
        elif s == '/':
            altitutes.append(altitutes[-1] + 1)

    edges = []
    n = len(altitutes)
    for i in range(n):
        level = altitutes[i]
        m_idx = i - 1
        for j in range(i - 1, -1, -1):
            if altitutes[j] > level:
                break
            if altitutes[j] == level:
                m_idx = j
                break
        edges.append([m_idx, i])

    areas = []
    begin, end = edges[-1]
    while begin != -1:
        area = calc_area(altitutes, begin, end)
        if area > 0:
            areas.append(area)
        begin, end = edges[begin]
    areas = areas[::-1]

    print(int(sum(areas)))
    print(*([len(areas)] + [*map(int, areas)]))

def calc_area(A, begin, end):
    if A[begin] != A[end]:
        return 0
    b_level = A[begin]
    area = 0
    for l1, l2 in zip(range(begin, end), range(begin+1, end + 1)):
        a1 = A[l1]
        a2 = A[l2]
        area += (b_level - a1 + b_level - a2) * 1 / 2
    return area

if __name__ == '__main__':
    main()
    # import cProfile
    # cProfile.run('main()')


### FIXED CODE ###

from sys import stdin
def stdinput():
    return stdin.readline().strip()

def main():
    altitutes = load_data()

    edges = create_edges(altitutes)

    # print(*edges)

    areas = calc_areas(altitutes, edges)

    print(int(sum(areas)))
    print(*([len(areas)] + [*map(int, areas)]))

def load_data():
    A = [0]
    for s in stdinput():
        if s == '\\':
            A.append(A[-1] - 1)
        elif s == '_':
            A.append(A[-1])
        elif s == '/':
            A.append(A[-1] + 1) 
    return A

def create_edges(A):
    st = [(0, None, 0)]
    highest = 0
    for i, a in enumerate(A[1:], 1):
        if st[-1][0] >= a:
            st.append((a, st[-1][2], i))
        else:
            begin = i - 1
            # NOTE: concat edges
            # this operation is performed every upforward(/) step,
            # and previous concated edges have altitute of (a - 1).
            while st[-1][1] != None and st[-1][0] == a - 1 and highest >= a:
                lev, begin, j = st.pop()
            highest = max(highest, a)
            st.append((a, begin, i))
        # print(*st)
    return [*map(lambda e: e[1:], st[1:])]

def calc_areas(A, edges):
    areas = []
    for begin, end in edges:
        area = calc_area(A, begin, end)
        if area > 0:
            areas.append(area)
    return areas    

def calc_area(A, begin, end):
    if A[begin] != A[end]:
        return 0
    b_level = A[begin]
    area = 0
    for l1, l2 in zip(range(begin, end), range(begin+1, end + 1)):
        a1 = A[l1]
        a2 = A[l2]
        area += (b_level - a1 + b_level - a2) * 1 / 2
    return area

if __name__ == '__main__':
    main()
    # import cProfile
    # cProfile.run('main()')
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(sorted([A.count(b) for b in range(1,N+1)], reverse=True))
"""
C = list(set(A))
B = [0 for i in range(len(C))]
for a in A:
    B[C.index(a)] += 1
#B = list(sorted([A.count(b) for b in set(A)], reverse=True))
B = list(sorted(B, reverse=True))
"""
print(sum(B[K:len(B)]))

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
B = {i:0 for i in set(A)}
for a in A:
    B[a] += 1
print(sum(sorted(B.values())[:-K]))
### BUGGY CODE ###

# Author: cr4zjh0bp
# Created: Tue Mar 17 19:50:06 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from itertools import permutations

n, m, R = na()
r = na()
abc = nan(m)
adj = [[0] * n for _ in range(n)]
for i in range(m):
    a, b, c = abc[i]
    a -= 1
    b -= 1
    adj[a][b] = c

dist = [[inf] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i == j:
            dist[i][j] = 0
        elif adj[i][j]:
            dist[i][j] = adj[i][j]

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

ans = inf
for p in permutations(r):
    res = 0
    for i in range(R - 1):
        f, t = p[i] - 1, p[i + 1] - 1
        res += dist[f][t]
    ans = min(ans, res)

print(ans)

### FIXED CODE ###

# Author: cr4zjh0bp
# Created: Tue Mar 17 19:50:06 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from itertools import permutations

n, m, R = na()
r = na()
abc = nan(m)
adj = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b, c = abc[i]
    a -= 1
    b -= 1
    adj[a][b] = c
    adj[b][a] = c

dist = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i == j:
            dist[i][j] = 0
        elif adj[i][j]:
            dist[i][j] = adj[i][j]

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

ans = inf
for p in permutations(r):
    res = 0
    for i in range(R - 1):
        f, t = p[i] - 1, p[i + 1] - 1
        res += dist[f][t]
    ans = min(ans, res)

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

def resolve():
    '''
    code here
    '''
    import collections
    N, K = [int(item) for item in input().split()]
    queries = [[int(item) for item in input().split()] for _ in range(N)]

    que = collections.deque()

    for num, val in queries:
        for _ in range(val):
            que.append(num)
    res_list = list(que)
    res_list.sort()

    print(res_list[K-1])

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    '''
    code here
    '''

    N, K = [int(item) for item in input().split()]
    queries = [[int(item) for item in input().split()] for _ in range(N)]

    queries.sort(key=lambda x:x[0])

    temp_que = []
    for num, val in queries:
        temp_que = num
        K -= val
        if K <= 0:
            break

    print(temp_que)

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

import bisect
n = int(input())
d_li = list(map(int,input().split()))
d_li.sort()
m = int(input())
t_li = list(map(int,input().split()))
t_li.sort()
for t in t_li:
    ind = bisect.bisect_left(d_li, t)
    if ind > len(d_li) -1:
        print('NO')
        exit()
    if d_li[ind] == t:
        d_li = d_li[ind+1:]
        #print(d_li)
    else:
        print('NO')
        exit()
print('YES')

### FIXED CODE ###

import bisect
n = int(input())
d_li = list(map(int,input().split()))
m = int(input())
t_li = list(map(int,input().split()))

import collections
d_cnt = collections.Counter(d_li)
t_cnt = collections.Counter(t_li)
#print(d_cnt,t_cnt)

for t in t_cnt.items():
    #print(d_cnt,d_cnt[t[0]],t[1])
    if d_cnt[t[0]] < t[1]:
        print('NO')
        exit()
print('YES')
### BUGGY CODE ###

from heapq import *
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
heapify(A)
for i in range(M):
    B, C = map(int, input().split())
    cnt = 0
    while cnt < B and cnt < N:
        x = heappop(A)
        if x < C:
            heappush(A, C)
        else:
            heappush(A, x)
            break
        cnt += 1
print(sum(A))

### FIXED CODE ###

from heapq import *
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
heapify(A)
B_C = [list(map(int, input().split())) for i in range(M)]
B_C.sort(key = lambda x : x[1], reverse = True)
for i in range(M):
    cnt = 0
    while cnt < B_C[i][0]:
        x = heappop(A)
        if x < B_C[i][1]:
            heappush(A, B_C[i][1])
        else:
            heappush(A, x)
            break
        cnt += 1
print(sum(A))
### BUGGY CODE ###

N = int(input())
str = []
for i in range(N):
    str.append(input())
num = [str.count(x) for x in set(str)]
max_list = []
for i in set(str):
    if(str.count(i) == max(num)):
        max_list.append(i)
max_list.sort()
for i in max_list :print(i)


### FIXED CODE ###

N = int(input())
str = {}
for i in range(N):
    key = input()
    if(key in str.keys()):
        str[key] += 1
    else:
        str[key] = 1
m = max(str.values())
str = sorted(str.items(),key=lambda x:x[1],reverse=True)
z = []
for i in range(len(str)):
    if(str[i][1] == m):
        z.append(str[i][0])
z.sort()
for i in z:print(i)
### BUGGY CODE ###

import sys
import heapq as h

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
nl = lambda: list(map(int, stdin.readline().split()))
nm = lambda: map(int, stdin.readline().split())

def main():
    n,m,l = nm()
    g = [list() for _ in range(n+1)]
    ans = [0]
    for _ in range(m):
        a,b,c = nm()
        if c > l:
            continue
        g[a].append((b,c))
        g[b].append((a,c))
    q = int(input())
    
    def move(tup,cost):
        if tup[1] + cost > 0:
            return (tup[0]+1,cost-l)
        return (tup[0],tup[1]+cost)
    
    for st in range(1,n+1):
        dist = [-1]*(n+1)
        que = [([0,-l],st)]
        while que:
            tup,v = h.heappop(que)
            if dist[v] != -1 and dist[v] < tup:
                continue
            dist[v] = tup
            for x,c in g[v]:
                new = move(tup,c)
                if new != -1 and dist[x] == -1:
                    h.heappush(que,(new,x))
        ans.append(dist)
    
    for _ in range(q):
        s,t = nm()
        if ans[s][t] == -1:
            print(-1)
        else:
            print(ans[s][t][0])

if __name__ == "__main__":
    main()

### FIXED CODE ###

n,m,l = map(int,input().split())
g = [[1<<30]*n for _ in range(n)]
for _ in range(m):
  a,b,c = map(int,input().split())
  g[a-1][b-1] = c
  g[b-1][a-1] = c
for i in range(n):
  g[i][i] = 0

def bell(g,n):
  for k in range(n):
    for i in range(n-1):
      for j in range(i+1,n):
        if g[i][j] > g[i][k] + g[k][j]:
          g[i][j] = g[i][k] + g[k][j]
          g[j][i] = g[i][j]
  return g

g = bell(g,n)
for i in range(n):
  for j in range(n):
    if i == j:
      g[i][j] = 0
    elif g[i][j] <= l:
      g[i][j] = 1
    else:
      g[i][j] = 1<<30
g = bell(g,n)

q = int(input())
for _ in range(q):
  s,t = map(int,input().split())
  if g[s-1][t-1]>>30:
    print(-1)
  else:
    print(g[s-1][t-1]-1)
### BUGGY CODE ###

def KnapSack(val, wt, n, W): 
      
    # matrix to store final result  
    mat = [[0 for i in range(W + 1)]  
              for i in range(2)] 
    # iterate through all items  
    i = 0
    while i < n: # one by one traverse  
                 # each element  
        j = 0 # traverse all weights j <= W 
          
        # if i is odd that mean till  
        # now we have odd number of  
        # elements so we store result   
        # in 1th indexed row  
        if i % 2 == 0: 
            while j < W: # check for each value  
                j += 1
                if wt[i] <= j: # include element  
                    mat[1][j] = max(val[i] + mat[0][j - 
                                     wt[i]], mat[0][j]) 
                else: # exclude element 
                    mat[1][j] = mat[0][j] 
                      
        # if i is even that mean till  
        # now we have even number  
        # of elements so we store  
        # result in 0th indexed row  
        else: 
            while j < W: 
                j += 1
                if wt[i] <= j: 
                    mat[0][j] = max(val[i] + mat[1][j - 
                                     wt[i]], mat[1][j]) 
                else: 
                    mat[0][j] = mat[1][j] 
        i += 1
    # Return mat[0][W] if n is  
    # odd, else mat[1][W]  
    if n % 2 == 0: 
        return mat[0][W] 
    else: 
        return mat[1][W] 
  
# Driver code
n,W = map(int,input().split())
val = [] 
wt = []  
for i in range(n):
    a,b = map(int,input().split())
    val.append(b)
    wt.append(a)
    
print(KnapSack(val, wt, n, W)) 

### FIXED CODE ###

from sys import stdin,stdout

print = stdout.write
input = stdin.readline
INF = 1e10
n,W = map(int,input().split())

wgt = [0]
val = [0]
for i in range(n):
    w,v = map(int,input().split())
    wgt.append(w)
    val.append(v)

max_val=sum(val)    
dp=[[INF for x in range(max_val+1)] for x in range(n+1)]
for i in range(n+1):
    dp[i][0]=0
for i in range(1,n+1):
    vi = val[i];wi = wgt[i]
    for V in range(1,max_val+1):
        if vi<= V:
            dp[i][V] = min(wi+dp[i-1][V-vi],dp[i-1][V])
        else:
            dp[i][V]=dp[i-1][V]
res = 0
for i in range(max_val,-1,-1):
    if dp[n][i] <= W:
        res = i
        break
print(str(res))
### BUGGY CODE ###


N = int(input())
S = input()

ans = 0
k = set('RGB')
for i in range(N):
	for j in range(i+1,N):
		ii = S[i]
		jj = S[j]
		if not ii==jj:
			tmp=list(k-set(ii+jj))[0]
			ans += S[j+1:].count(tmp)
			if 2*j-i<N and S[2*j-i]==tmp:
				ans -= 1
print(ans)

### FIXED CODE ###

import sys
from collections import defaultdict
d = defaultdict(str)
N = int(sys.stdin.readline())
S = sys.stdin.readline()

ans = 0
k = 'RGB'
for i in range(N):
	for j in range(i+1,N):
		if not S[i]==S[j]:
			tmp =k.replace(S[i],'')
			tmp = tmp.replace(S[j],'')
			if d[str(j+1)+tmp]=='':
				p = S[j+1:].count(tmp)
				d[str(j+1)+tmp] = p
				ans += p
				if 2*j-i<N and S[2*j-i]==tmp:
					ans-= 1
					
			else:
				ans +=d[str(j+1)+tmp]
				if 2*j-i<N and S[2*j-i]==tmp:
					ans -=1
print(ans)