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

S = raw_input();

cnt = 0;

while True:
	for i in range(len(S)):
		tmp = S.replace('01', '', 1);
		if S != tmp:
			cnt += 2;
			S = tmp;
			break;

		tmp = S.replace('10', '', 1);
		if S != tmp:
			cnt += 2;
			S = tmp;
			break;

	if len(set(S)) <= 1:
		break;

print(cnt);

### FIXED CODE ###

S = raw_input();

S1 = S.count('1');
S0 = S.count('0');

if S1 > S0:
	print S0 * 2;

else:
	print S1 * 2;
### BUGGY CODE ###

dp=[1]*(10**5+1)
dp[0],dp[1]=0,0
for i in range(2,10**5+1):
  if dp[i]==0:
    continue
  j=i
  while j+i<=10**5:
    j+=i
    if dp[j]==1:
      dp[j]-=1
ni=[0]*(10**5+1)
for i in range(2,10**5+1):
  if dp[i]==1 and dp[(i+1)//2]==1:
    ni[i]=1

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

### FIXED CODE ###

dp=[1]*(10**5+1)
dp[0],dp[1]=0,0
for i in range(2,10**5+1):
  if dp[i]==0:
    continue
  j=i
  while j+i<=10**5:
    j+=i
    if dp[j]==1:
      dp[j]-=1
      
ni=[0]*(10**5+1)
for i in range(2,10**5+1):
  if dp[i]==1 and dp[(i+1)//2]==1:
    ni[i]=1

ru=[0]*(10**5+1)
for i in range(1,10**5+1):
  ru[i]=ru[i-1]+ni[i]

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

import collections
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
d=collections.Counter(A)
for i in range(Q):
  B,C=map(int,input().split())
  if d[C] in d:
    d[C]+=d[B]
  else:
    d[C]=d[B]
  d[B]=0
  ans=0
  for j in d:
    ans += j*d[j]
  print(ans)

### FIXED CODE ###

import collections
N=int(input())
A=list(map(int,input().split()))
s=sum(A)
Q=int(input())
d=collections.Counter(A)
for i in range(Q):
  B,C=map(int,input().split())
  s += d[B]*C - d[B]*B
  print(s)
  if C in d:
    d[C]+=d[B]
  else:
    d[C]=d[B]
  d[B]=0
### BUGGY CODE ###

n,c = map(int,input().split())
l = [[0,0] for _ in range(n)]
dp1 = [0 for _ in range(n)]
dp2 = [0 for _ in range(n)]
for i in range(n):
    l[i] = list(map(int, input().split()))

dp1[0] = l[0][1] - l[0][0]
dp2[0] = l[-1][1] - c + l[-1][0]
for i in range(1,n):
    dp1[i] = dp1[i-1] + l[i][1] - l[i][0] + l[i-1][0]
    dp2[i] = dp2[i-1] + l[-i-1][1] - l[-i][0] + l[-i-1][0]

ans = max(max(dp1),max(dp2))
tmp = 0
for i in range(n-1):
    for j in range(n-i-1):
        tmp = dp1[i]+dp2[j]-l[i][0]
        if ans < tmp:
            ans = tmp
tmp2 = 0
for i in range(n-1):
    for j in range(n-i-1):
        tmp2 = dp2[i] + dp1[j] - c + l[-i-1][0]
        if ans < tmp2:
            ans = tmp2

if ans > 0:
    print(ans)
else:
    print(0)

### FIXED CODE ###

n,c = map(int,input().split())
l = [[0,0] for _ in range(n)]
dp1 = [0 for _ in range(n)]
dp2 = [0 for _ in range(n)]
mx1 = [0 for _ in range(n)]
mx2 = [0 for _ in range(n)]
for i in range(n):
    l[i] = list(map(int, input().split()))


dp1[0] = l[0][1] - l[0][0]
dp2[0] = l[-1][1] - c + l[-1][0]
tmp = dp1[0]
tmp2 = dp2[0]
mx1[0] = dp1[0]
mx2[0] = dp2[0]
for i in range(1,n):
    dp1[i] = dp1[i-1] + l[i][1] - l[i][0] + l[i-1][0]
    dp2[i] = dp2[i-1] + l[-i-1][1] - l[-i][0] + l[-i-1][0]
    if tmp < dp1[i]:
        mx1[i] = dp1[i]
        tmp = dp1[i]
    else :
        mx1[i] = tmp
    if tmp2 < dp2[i]:
        mx2[i] = dp2[i]
        tmp2 = dp2[i]
    else :
        mx2[i] = tmp2

ans = max(max(dp1),max(dp2))

tmp = [0 for _ in range(n-1)]
tmp2 = [0 for _ in range(n-1)]
for i in range(n-1):
    tmp[i] = dp1[i] + mx2[-i-2] - l[i][0]
    if ans < tmp[i]:
        ans = tmp[i]

for i in range(n-1):
    tmp2[i] = dp2[i] + mx1[-i-2] - (c - l[-i-1][0])
    if ans < tmp2[i]:
        ans = tmp2[i]

if ans > 0:
    print(ans)
else:
    print(0)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

ans = 0
n_iter_r = N//R + 1
n_iter_g = N//G + 1

for r in range(n_iter_r):
    for g in range(n_iter_g):
        if N - R*r - G*g < 0:
            continue
        else:
            if (N - R*r - G*g)%B==0:
                if (N - R*r - G*g)//B >= 0:
                    ans += 1
                    
print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())

ans = 0
n_iter_r = N//R + 1
n_iter_g = N//G + 1

for r in range(n_iter_r):
    for g in range(n_iter_g):
        nokori = N - R*r - G*g
        if nokori < 0:
            break
        else:
            if nokori%B==0:
                ans += 1

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

N = int(input())

S = [input() for i in range(N)]
kinds = set(S)
result = {}

for i in kinds:
    result[i] = S.count(i)
result_max = sorted([i for i in result.keys() if result[i] == max(result.values())])

for r in result_max:
    print(r)

### FIXED CODE ###

import collections


N = int(input())

S = [input() for i in range(N)]

count = collections.Counter(S)


mx = max(count.values())

result = [key for key, val in count.items() if val == mx]
print("\n".join(sorted(result)))
### BUGGY CODE ###

import sys
import time
def anscheck(x,y,d,e,f):
    # print "%.3f %.3f %.3f %.3f %.3f"%(x,y,d,e,f)
    if d*x+e*y == f:
        # print "correct!"
        print "%.3f %.3f"%(x,y)
        return True
    else:
        # print "different"
        return False
for line in sys.stdin:
    a,b,c,d,e,f = map(float,line.split())
    i=1
    while True:
        if (a*i-c) % b ==0:
            x=i
            if a*i-c>0:
                if b>0:
                    y= -((a*i-c)/b)
                else:
                    y= (a*i-c)/b
            elif a*i-c<0:
                if b>0:
                    y= -((a*i-c)/b)
                else:
                    y= (a*i-c)/b
            else:
                pass
            if anscheck(x,y,d,e,f):
                break
        # if b*i-c % a == 0:
        #     x=i
        #     if b*i>c:
        #         y= -(b*i-c)/a
        #     elif b*i<c:
        #         y= (b*i-c)/a
        #     else:
        #         pass
        #     anscheck(x,y,d,e,f)
        if (a*(-i)-c) % b ==0:
            x=-i
            if a*(-i)-c>0:
                if b>0:
                    y= -((a*(-i)-c)/b)
                else:
                    y= (a*(-i)-c)/b
            elif a*(-i)-c<0:
                if b>0:
                    y= -((a*(-i)-c)/b)
                else:
                    y= (a*(-i)-c)/b
            else:
                pass
            if anscheck(x,y,d,e,f):
                break
        # if b*(-i)-c % a ==0:
        #     x=-i
        #     if b*(-i)>c:
        #         y= -(b*(-i)-c)/a
        #     elif b*(-i)<c:
        #         y= (b*(-i)-c)/a
        #     else:
        #         pass
        #     anscheck(x,y,d,e,f)
        i+=1.0

### FIXED CODE ###

import sys
import time
#1.2 2.8 4.12 1.5 3.0 4.5
for line in sys.stdin:
    a1,b1,c1,a2,b2,c2 = map(float,line.split())
    i=0
    x = (c1*b2-c2*b1) / (a1*b2-a2*b1)
    y = (a1*c2-a2*c1) / (a1*b2-a2*b1)
    if "-0" in str(x):
        x = 0.0
    print "%.3f %.3f"%(x,y)
### BUGGY CODE ###

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

for _ in range(K):
    H[H.index(max(H))] = 0
    
print(sum(H))

### FIXED CODE ###

#C
import heapq

N, K = map(int, input().split())
H = list(map(int, input().split()))
H = list(map(lambda x: x*(-1), H))
heapq.heapify(H)

if K >= N:
    print(0)
else:
    for _ in range(K):
        heapq.heappop(H)
    print(-sum(H))
### BUGGY CODE ###

N, P=map(int,input().split())
S = input()
def ma25():
  ret = 0
  for i in range(N):
    if int(S[i])%P == 0:
      ret+=(i+1)
  print(ret)

def ma():
  dp = [0]*P
  dp[0] = 1
  for i in range(N-1,-1,-1):
    dp[int(S[i:])%P] += 1
  ret = 0
  for m in dp:
    ret += m*(m-1)//2
  print(ret)

if P == 2 or P == 5:
  ma25()
else:
  ma()

### FIXED CODE ###

N, P=map(int,input().split())
S = list(map(int,list(input())))

def ma25():
  ret = 0
  for i in range(N):
    if S[i]%P == 0:
      ret+=(i+1)
  print(ret)

def ma():
  dp = [0]*P
  dp[0] = 1
  r = 0
  for i in range(N-1,-1,-1):
    r = ((S[i]*pow(10,N-1-i,P))+r)%P
    dp[r] += 1
  ret = 0
  for m in dp:
    ret += m*(m-1)//2
  print(ret)

if P == 2 or P == 5:
  ma25()
else:
  ma()
### BUGGY CODE ###

s = input()

count = s.count('0000') +s.count('2019') + s.count('4038') + s.count('8076')

for i in range(0, len(s)-4):
    for j in range(i+5, len(s)+1):
        if int(s[i:j]) % 2019 == 0:
            count += 1

print(count)

### FIXED CODE ###

s = input()

MOD = 2019
d = [0] * MOD
d[0] = 1
r = 0
t = 1
for i in reversed(s):
    r += int(i) * t
    r %= MOD
    t *= 10
    t %= MOD
    d[r] += 1

print(sum(i * (i - 1) // 2 for i in d))
### BUGGY CODE ###

N,K= map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = -1000000000

for i in range(N):
    S = []
    j = P[i]-1
    S.append(C[j])

    while i != j:
        j = P[j]-1
        S.append(S[-1] + C[j])

    if K <= len(S):
        score = max(S[:K])

    elif S[-1] <= 0:
        score = max(S)
    
    else:
        score1 = K//len(S) * S[-1]
        r = K%len(S)
        if r != 0:
            score1 += max(0, max(S[:r]))
        score2 = (K//len(S)-1)*S[-1] + max(S)
        score = max(score1, score2)
    ans = max(ans, score)
print(ans)

### FIXED CODE ###

N,K= map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = -1000000000

for i in range(N):
    S = []
    j = P[i]-1
    S.append(C[j])

    while i != j:
        j = P[j]-1
        S.append(S[-1] + C[j])

    if K <= len(S):
        score = max(S[:K])

    elif S[-1] <= 0:
        score = max(S)
    
    else:
        score1 = K//len(S) * S[-1]
        r = K%len(S)
        if r != 0:
            score1 += max(0, max(S[:r]))
        score2 = (K//len(S)-1)*S[-1] + max(S)
        score = max(score1, score2)
    ans = max(ans, score)
print(ans)
### BUGGY CODE ###

def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

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

    ans = 0
    c = Counter(A)
    B = sorted(c.keys(), reverse=True)

    for b in B:
        if c[b] == 0:
            continue
        a = (2 ** b.bit_length()) - b
        if a == b:
            cur = c[b]//2
        else:
            if a in c.keys():
                cur = min(c[a], c[b])
            else:
                cur = 0
        ans += cur
        # c[b] -= cur
        c[a] -= cur

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

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

    ans = 0
    A.sort(reverse=True)
    c = Counter(A)

    for b in A:
        if c[b] == 0:
            continue
        a = (2 ** b.bit_length()) - b
        if a == b:
            cur = c[b]//2
        else:
            cur = min(c[a], c[b])
        ans += cur
        c[b] -= cur
        c[a] -= cur
        # print(a, b, c, ans)

    print(ans)


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

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

def search(first, count):
  change = 0
  past = "1"
  for i in range(first, len(S)):
    now = S[i]
    if past != now:
      change += 1
      if change == count*2:
        #print(S[first], S[i])
        for j in range(i, len(S)):
          if "1" != S[j]:
            #print(j, first)
            return j-first
    past = S[i]
  #print(len(S), first)
  return len(S)-first

max_len = 0
past = ""
for i in range(len(S)):
  now = S[i]
  if past != now:
    #print(i, S[i], search(i, K))
    max_len = max([search(i, K), max_len])
  past = S[i] 
  

#print(N, K, S)
print(max_len)

### FIXED CODE ###

N, K = list(map(int, input().split()))
S = input()
 
S += "X"
i = 0
j = 0
max_len = 0
change = 0 if S[0] != "0" else 1
while j < len(S)-1:
  if change <= K:
    #print(i, j)
    max_len = max([j-i+1, max_len])
    if S[j:j+2] == "10":
      change += 1
    j += 1
  else:
    if S[i:i+2] == "01":
      change -= 1
    i += 1

print(max_len)
### BUGGY CODE ###

n,m,k = map(int,input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
import sys
sys.setrecursionlimit(10**6)
maxc = 0
a_i=0
b_i=0
def dfs(a_i,b_i,t,cnt):
    global maxc
    
    if(a_i==n and b_i==m):
        maxc = m+n
        return
    if(k < t):
        maxc = max(maxc,cnt-1)
        return 
    if(a_i < n):
        dfs(a_i+1,b_i,A[a_i]+t,cnt+1)

    if(b_i < m):
        dfs(a_i,b_i+1,B[b_i]+t,cnt+1)



        
dfs(0,0,0,0)
print(maxc)

### FIXED CODE ###

import bisect

n,m,k = map(int,input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

A_sum = [0]*(n+1)
B_sum = [0]*(m+1)

for i in range(n):
    A_sum[i+1] = A_sum[i] + A[i]

for i in range(m):
    B_sum[i+1] = B_sum[i] + B[i]

A_limit = bisect.bisect_right(A_sum,k) - 1
mc = 0
B_i = 0
for i in range(A_limit,-1,-1):
    remain_k = k - A_sum[i]
    while((remain_k-B_sum[B_i])>=0):
        B_i += 1
        if(B_i==(m+1)):
            break
    B_i -= 1
    mc = max(mc,(i+B_i))

print(mc)
### BUGGY CODE ###

n, m = map(int, input().split())
ab = set([tuple(map(int, input().split())) for _ in range(m)])

c = []
flag = False
for i in ab:
    a, b = i[0], i[1]
    for i in c:
        if a in i or b in i:
            i.add(a)
            i.add(b)
            if len(i) == n:
                flag = True
    else:
        c.append(set())
        c[-1].add(a)
        c[-1].add(b)
    if flag:
        break
if m == 0:
    print(1)
else:
    print(max(map(len, c)))

### FIXED CODE ###

class Union:
    def __init__(self, n):
        self.parents = [-1] * n
    
    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            return self.root(self.parents[x])
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

uni = Union(n)
for a, b in ab:
    a -= 1
    b -= 1
    uni.unite(a, b)
print(-min(uni.parents))
### BUGGY CODE ###

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

friend_list = []
for i in range(M):
  pair = list(map(int, input().split()))
  friend_list.append(set(pair))

group_num_people = []
for i, group in enumerate(friend_list):
  for j in range(M):
    if i == j:
      continue
    else:
      target = friend_list[j]
      if len(group.intersection(target)) >= 1:
        group = group.union(target)
  group_num_people.append(len(group))


if M == 0:
  print(1)
else:
  print(max(group_num_people))

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


class UnionFind():
    """ UnionFindはグループの分割はできないことに注意 """
    def __init__(self, n):
        """
            n: 要素数
            parents: 親を示す、-1の場合、自身の親がいない(頂点)であることを示す
        """
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """
        親の要素が何かを調べる
        同じ要素であれば、同じグループに所属することを示す
        探索しながら、親を頂点につなぎ直すことで、効率的にまとめることができる
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        xとyの所属するグループをまとめる
        """
        x = self.find(x)
        y = self.find(y)

        # 同じ親だった場合、既にグループはまとまっているので処理を終了する
        if x == y:
            return

        # 浅い方を深い方に繋ぐようにする
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def most_depth_root(self):
        return -min(self.parents)


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

union_find = UnionFind(N)
for i in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    union_find.union(x, y)

print(union_find.most_depth_root())
### BUGGY CODE ###

import copy
import math

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

sorted_As = sorted(As,reverse = True)
cut_As = copy.copy(sorted_As)
count_list = [0]*len(sorted_As)

for i in range(K):
    index = cut_As.index(max(cut_As))
    count = count_list[index]
    count_list[index] += 1
    cut_As[index] = sorted_As[index] / (count+2)

'''
for i in range(K):
    count = count_list[0]
    count_list[0] += 1
    cut_As[0] = sorted_As[0] / (count+2)
    cut_As,sorted_As,count_list = (list(x) for x in zip(*sorted(zip(cut_As,sorted_As,count_list),reverse = True)))
'''

print(math.ceil(max(cut_As)))


### FIXED CODE ###

def judge(As,K,C):
    count = 0
    for i in range(len(As)):
        if As[i]%C == 0:
            m = As[i]//C - 1
        else:
            m = As[i]//C
        count += m
    if count <= K:
        return True
    else:
        return False

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

l = 0
r = max(As)
while(r-l>1):
    mid = (l+r)//2
    if judge(As,K,mid):
        r = mid -1
    else:
        l = mid + 1
if judge(As,K,r):
    print(r)
else:
    print(r+1)
### BUGGY CODE ###

h,k=list(map(int,input().split()))

def bupdp(l,h,k):
    dp=[0]*(h+1)
    dp[0] = 0
    for i in range(0,h):
        if i>k:
            mini = 999999999
            for j in range(1,k+1):
                mini = min(mini,dp[i-j]+abs(l[i]-l[i-j]))                
            dp[i] = mini

        if i<=k:
            minim = 999999999
            for j in range(1,i+1):
                minim = min(minim,dp[i-j]+abs(l[i]-l[i-j])) 
            dp[i] = minim
        # if i==1:
            # dp[i] = abs(l[i]-l[i-1])
        if i<1:
            dp[i] = 0   
    # print(dp)
    return dp[-2]

l = list(map(int,input().split()))
print(bupdp(l,h,k))


### FIXED CODE ###

h,k=list(map(int,input().split()))
def bupdp(l,h,k):
    dp=[0]*(h+1)
    dp[0] = 0
    for i in range(0,h):
        if i>k:
            mini = min([dp[i-j]+abs(l[i]-l[i-j]) for j in range(1,k+1)])             
            dp[i] = mini
        if i<=k and i!=0:
            minim = min([dp[i-j]+abs(l[i]-l[i-j]) for j in range(1,i+1)])
            dp[i] = minim
        if i<1:
            dp[i] = 0
    return dp[-2]

l = list(map(int,input().split()))
print(bupdp(l,h,k))
### BUGGY CODE ###

N,M=map(int,input().split())
lists = []
for n in range(N):
  lists.append([])
items = []
for m in range(M):
  p, y = map(int, input().split())
  items.append(tuple([p, y]))
  lists[p-1].append(y)

sorted_lists = []

for l in range(len(lists)):
  sort_list = sorted(lists[l])
  sorted_lists.append(sort_list)

for p, y in items:
  index = sorted_lists[p-1].index(y)
  f = lambda x: ('0' * (6 - len(str(x))) +  str(x))
  print(f(p) + f(index+1))

### FIXED CODE ###

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

lists = [[] for _ in range(N)]
items = [list(map(int, input().split())) for _ in range(M)]
for p, y in items:
  lists[p-1].append(y)

dic = {}

for n in range(N):
  lists[n].sort()  

for n in range(N):
  l = lists[n]
  count = 1
  for i in l:
    dic[i] = count
    count+=1

for p, y in items:
  print("{:06g}{:06g}".format(p,dic[y]))
### BUGGY CODE ###

S = input()
Q = int(input())

res = S

def add_char(s, f, c):
  if(f == "1"):
    return c + s
  else:
    return s + c

for _ in range(Q):
  q = input().split()
  
  if(q[0] == '1'): # Ti = 1
    res = res[::-1]
  
  else: #Ti = 2
    res = add_char(res, q[1], q[2])


print(res)

### FIXED CODE ###

S = input()
Q = int(input())

res = S

is_rev = False

before = []
after = []

def add_char(s, f, c, is_rev):
  if(f == "1"):
    before.append(c)
  else:
    after.append(c)

for _ in range(Q):
  q = input().split()
  
  if(q[0] == '1'): # Ti = 1
    is_rev = not is_rev
    before, after = after, before
  
  else: #Ti = 2
    add_char(res, q[1], q[2], is_rev)

before.reverse()

res = "".join(before) + (res[::-1] if is_rev else res) + "".join(after)

print(res)
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
_sum = 0
y = len(p)
for i in range(y):
    a = p[i]
    #print("a:" +str(a))
    for j in range(y-i-1):
        b=p[i+j+1]
        #print("b:"+str(b))
        _sum += (a*b)
        #print("_sum:"+str(_sum))
print(_sum % (10**9+7))
    

### FIXED CODE ###

n = int(input())
t = 10**9+7
z = list(map(int,input().split() ))
_sum = 0
x = sum(z)
y = len(z)
for i in range(y-1):
    x = x-z[i]
    _sum += (z[i]*x)
        #print("_sum:"+str(_sum))
print(_sum%t)
### BUGGY CODE ###

def main():
    from bisect import bisect_right as br
    from sys import stdin
    input=stdin.readline
    n = int(input())
    a = sorted(list(map(int, input().split())))
    b = sorted(list(map(int, input().split())), reverse=True)
    #n = 100000
    #a = [i+1 for i in range(n)]
    #b = [2*i+2 for i in range(n)]
    m = n % 2
    xor = 0
    for i in b:
        xor ^= i
    for i in range(n):
        b[i] = 2**28 - b[i]
    ans = 0
    for loop in range(28, -1, -1):
        j = pow(2, loop)
        k = (xor & j) // j
        temp = br(b, j-1)
        for i in range(temp, n):
            b[i] -= j
        b.sort()
        x = k*m % 2
        b0 = br(b, 0) % 2
        for i in a:
            k2 = m * (i & j) // j
            x += (k2 + br(b, i % j) - b0) % 2
        ans += (x % 2)*j
    print(ans)


main()


### FIXED CODE ###

def main():
    from bisect import bisect_right as br
    n = int(input())
    a = sorted(list(map(int, input().split())))
    b = sorted(list(map(int, input().split())), reverse=True)
    m = n % 2
    xor = 0
    for i in b:
        xor ^= i
    for i in range(n):
        b[i] = 2**28 - b[i]
    ans = 0
    for loop in range(28, -1, -1):
        j = pow(2, loop)
        k = (xor & j) // j
        temp = br(b, j-1)
        for i in range(temp, n):
            b[i] -= j
        b.sort()
        temp = br(a, j-1)
        for i in a[:temp]:
            k += (i & j) // j
        for i in range(temp, n):
            k += (a[i] & j) // j
            a[i] -= j
        x = (k+br(b, 0))*m % 2
        a.sort()
        l = 0
        for i in a:
            while l < n:
                if i >= b[l]:
                    l += 1
                else:
                    break
            x += l % 2
        ans += (x % 2)*j
    print(ans)


main()
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, N = MAP()
A = [0]*N
B = [0]*N

for i in range(N):
    A[i], B[i] = MAP()

dp = [[INF]*(H+max(A)+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for j in range(H+max(A)):
        if j < A[i]:
            dp[i+1][j] = dp[i][j]
        dp[i+1][j] = min(dp[i][j], dp[i+1][j-A[i]]+B[i])

print(min(dp[N][H:]))


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, N = MAP()
A = [0]*N
B = [0]*N

for i in range(N):
    A[i], B[i] = MAP()

dp = [[INF]*(H+max(A)+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for j in range(H+max(A)):
        if j < A[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j-A[i]]+B[i])

print(min(dp[N][H:]))