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

from itertools import combinations

N, K = map(int, input().split(' '))
fruit_prices = tuple(map(int, input().split(' ')))

min_price = sum(fruit_prices)

for comb in combinations(fruit_prices, K):
  min_price = min(sum(comb), min_price)

print(min_price)

### FIXED CODE ###

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

fruit_prices.sort()

min_price = 0

for i in range(K):
  min_price += fruit_prices[i]

print(min_price)
### BUGGY CODE ###

n, k = [int(e) for e in input().split()]
h = [int(e) for e in input().split()]
cost = [0] * n
for i in range(1, n):
  cost[i] = min(abs(h[i] - h[j]) + cost[j] for j in range(max(0, i - k), i))
print(cost[n - 1])


### FIXED CODE ###

n, k = [int(e) for e in input().split()]
h = [int(e) for e in input().split()]
cost = [0] * n
cost[1] = abs(h[1] - h[0])
for i in range(1, n):
  cost[i] = min(abs(h[i] - h[j]) + cost[j] for j in range(max(0, i - k), i))
print(cost[n - 1])
### BUGGY CODE ###

K = int(input())
x = 0
count = 0
if K <= 12:
  print(K)
  exit()
while count < K:
  x = int(x)
  x += 1
  x = str(x)
  for i in range(1,len(x)):
    if abs(int(x[i])-int(x[i-1])) > 1:
      count -= 1
      break
  count += 1
print(x)

### FIXED CODE ###

from collections import deque
K = int(input())
Q = deque([i for i in range(1,10)])

for _ in range(K-1):
    q = Q.popleft()
    if q%10 != 0:
        Q.append(10*q+(q%10)-1)
    Q.append(10*q+(q%10))
    if q%10 != 9:
        Q.append(10*q+(q%10)+1)
print(Q.popleft())
### BUGGY CODE ###

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

mod = 998244353
ans = 0

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    x = 1
    y = 1
    for i in range(r):
        x *= (n - i)
        y *= (i + 1)
        x %= mod
        y %= mod
    return (x * modinv(y, mod)) % mod


for i in range(k+1):
    ans += m * combination(n-1, i, mod) * pow(m-1, n-i-1, mod)
    ans %= mod

print(ans)



### FIXED CODE ###

import sys

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """

    def __init__(self, n_max, mod=998244353):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

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

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

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

mod = 998244353
ans = 0

comb = Combination(2*10**5)


for i in range(k+1):
    ans += m * comb(n-1, i) * pow(m-1, n-i-1, mod)
    ans %= mod

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

import sys
mod = 10**9+7
N = int(sys.stdin.readline())
A = tuple(map(int, sys.stdin.readline().split()))
B = []
ans = 0
C = [0 for i in range(60)]
for i in A:
    for l in range(60):
        if ((i >> l) & 1) == 1:
            C[l] += 1
for i in range(60):
    t = C[i]
    ans = (ans + t*(N-t)*(2**i)) % mod
print(ans)

### FIXED CODE ###

import sys
mod = 10**9+7
N = int(sys.stdin.readline())
A = tuple(map(int, sys.stdin.readline().split()))
B = []
ans = 0
C = [0 for i in range(60)]
for i in A:
    for l in range(60):
        if ((i >> l) & 1) == 1:
            C[l] += 1
for i in range(60):
    t = C[i]
    ans = (ans + t*(N-t)*(2**i)) % mod
print(ans)
### BUGGY CODE ###

N, K = input().split(' ')
N = int(N)
K = int(K)
N1 = abs(N-K)
NB = [N, N1]
while NB[-1] < NB[-2]:
  NN = abs(NB[-1]-K)
  NB.append(NN)
else:
  print(NB[-2])

### FIXED CODE ###

N, K = input().split(' ')
NA = int(N)
K = int(K)
if NA - K > K:
  NA = NA - K*(NA//K - 1)
N1 = abs(NA-K)

while N1 < NA:
  NA = N1
  N1 = abs(N1-K)
else:
  print(NA)
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    edge = [[] for _ in range(N+1)]
    for i in range(2,N+1):
        u = NI()
        edge[u].append(i)

    def depth(u):
        ret = 0
        d = []
        for v in edge[u]:
            d.append(depth(v))
        d.sort(reverse=True)
        for i,x in enumerate(d):
            ret = max(ret,i+x+1)
        return ret

    ans = depth(1)
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    edge = [[] for _ in range(N+1)]
    cnt = [0] * (N+1)
    for i in range(2,N+1):
        u = NI()
        edge[i].append(u)
        cnt[u] += 1

    q = collections.deque()
    for i in range(2,N+1):
        if cnt[i] == 0:
            q.append((i,0))
            cnt[i] = 1


    out = [[] for _ in range(N+1)]
    ret = 0
    while q:
        u,d = q.popleft()
        out[u].append(d)
        if len(out[u]) == cnt[u]:
            out[u].sort(reverse=True)
            ret = 0
            for i,x in enumerate(out[u]):
                ret = max(ret,i+x+1)
            if u == 1: break
            for v in edge[u]:
                q.append((v,ret))


    print(ret-1)

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

N=int(input())
a=list(map(int,input().split()))
A=[0]*N
B=[]
count=0
for i in range(N//2,N):
    if a[i]==1:
        A[i]=1
        count=count+1
        B.append(i+1)
for i in range(N//2)[::-1]:
    asum=0
    for j in range(i,N):
        if (j+1)%(i+1)==0:
            asum=asum+A[j]
    if asum%2==a[i]:
        A[i]=0
    else:
        A[i]=1
        B.insert(0,i+1)
        count=count+1
print(count)
if count!=0:
    print(*B)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
A=[0]*N
B=[]
for i in range(N//2,N):
    if a[i]==1:
        A[i]=1
        B.append(i+1)
for i in range(N//2)[::-1]:
    asum=0 
    x=i+1
    for j in range(i,N,x):
        asum=asum+A[j]
    if asum%2!=a[i]:
        A[i]=1
        B.append(i+1)
count=sum(A)
print(count)
if count!=0:
    print(*B)
### BUGGY CODE ###

S = input()
rem = [0]*2019

n = 0
d = 0

for s in S[::-1]:
    n = n%2019 + (int(s)*10**d)%2019
    tmp = n%2019
    rem[tmp] += 1
    d += 1
    
ans = 0
for i in rem:
    ans += ((i*(i-1))//2)

print(ans+rem[0])

### FIXED CODE ###

S = input()[::-1]
rem = [0]*2019

n = 0
d = 1

for s in S:
    n = n%2019 + (int(s)*d)%2019
    tmp = n%2019
    rem[tmp] += 1
    d *= 10
    d %= 2019
    
ans = 0
for i in rem:
    ans += ((i*(i-1))//2)

print(ans+rem[0])
### BUGGY CODE ###

import numpy as np

n = int(input())
a = [0] * n
for i in range(n):
    a[i] = int(input())

arr = np.array(a)
jun = np.argsort(arr)
jun = list(jun)

ans = 0
while jun:
    ans += 1
    i = jun.pop()
    for j in range(i):
        if a[j] != a[i]:
            try:
                jun.remove(j)
            except:
                ValueError

print(ans)

### FIXED CODE ###

# 広義最長部分増加数列の長さを求めるdef
# 配列LIS自体は広義最長部分増加文字列ではない
import bisect
def lis(seq):
    LIS = [seq[0]]
    for i in range(1, len(seq)):
        if seq[i] >= LIS[-1]:
            LIS.append(seq[i])
        else:
            LIS[bisect.bisect_right(LIS, seq[i])] = seq[i]
    return(len(LIS))

n = int(input())
a = [0] * n
for i in range(n):
    a[i] = int(input())

b = a[::-1]
print(lis(b))
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

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

INF = -1
Gmap = [list(input()) for _ in range(H)]
next_q = deque([])

def dfs_settings():
    #複数
    for h in range(H):
        for w in range(W):
            if Gmap[h][w]=='#':
                next_q.append([h,w])
                Gmap[h][w]=0

def dfs():
    ret = 0
    while len(next_q)!=0:
        #スタック取り出し(先頭)幅優先
        h,w = next_q.popleft()
        lv=Gmap[h][w]+1
        hs, ws = h + 0 , w + 1
        if ws<W and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h + 1 , w + 0
        if hs<H and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h + 0 , w - 1
        if ws>=0 and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h - 1 , w + 0
        if hs>=0 and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
    return ret

def main():
    dfs_settings()
    ret = dfs()
    print(ret)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

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

INF = -1
Gmap = [list(input()) for _ in range(H)]
next_q = deque([])

def dfs_settings():
    #複数
    for h in range(H):
        for w in range(W):
            if Gmap[h][w]=='#':
                next_q.append([h,w])
                Gmap[h][w]=0

def dfs():
    ret = 0
    while len(next_q)!=0:
        #スタック取り出し(先頭)幅優先
        h,w = next_q.popleft()
        lv=Gmap[h][w]+1
        hs, ws = h + 0 , w + 1
        if ws<W and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h + 1 , w + 0
        if hs<H and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h + 0 , w - 1
        if ws>=0 and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h - 1 , w + 0
        if hs>=0 and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
    return ret

def main():
    dfs_settings()
    ret = dfs()
    print(ret)

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

from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    l = list(map(int, input().split()))
    l.sort()

    ans = 0

    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            a = l[i]
            b = l[j]
            k = j + 1
            while k < n and l[k] < a + b:
                ans += 1
                k += 1

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


### FIXED CODE ###

from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    l = list(map(int, input().split()))
    l.sort()

    l_c = [0] * 2001

    for li in l:
        l_c[li] += 1
    for i in range(2000):
        l_c[i + 1] += l_c[i]

    ans = 0

    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            ans += l_c[l[i] + l[j] - 1] - j - 1

    print(ans)


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

import math
import bisect
n=int(input())
a=list(map(int,input().split()))
a.sort()
b=[]
for i in range(1,50):
  b.append(2**i)
ct=0
check=[0]*n
for i in range(n-1,-1,-1):
  if check[i]==0:
    check[i]=1
    x=math.floor(math.log2(a[i]))
    x=b[x]-a[i]
    y=bisect.bisect_left(a,x)
    if a[y]==x:
      if check[y]==0:
        check[y]=1
        ct+=1
      else:
        while a[y]==x:
          if a[y]==x and check[y]==0:
            check[y]=1
            ct+=1
            break
          y+=1
          if y==n:
            break
print(ct)

### FIXED CODE ###

import math
import bisect
n=int(input())
a=list(map(int,input().split()))
a.sort()
b=[]
for i in range(1,50):
  b.append(2**i)
ct=0
check=[1]*n
for i in range(n-1,-1,-1):
  if a[i]==1:
    break
  if check[i]==1 and a[i] not in b:
    check[i]=0
    x=math.floor(math.log2(a[i]))
    x=b[x]-a[i]
    y=bisect.bisect_left(a,x)
    z=bisect.bisect_right(a,x)
    t=bisect.bisect_left(check[y:z],1)+y
    if t!=z:
      check[t]=0
      ct+=1

ctb=0
w=1
for i in range(n):
  if a[i] in b or a[i]==1:
    if a[i]==w:
      if check[i]==1:
        ctb+=1
    else:
      ct+=ctb//2
      w=a[i]
      if check[i]==1:
        ctb=1
      else:
        ctb=0
  else:
    ct+=ctb//2
    ctb=0
ct+=ctb//2

print(ct)
### BUGGY CODE ###

def merge(A,left,mid,right):
    n1=mid-left
    n2=right-mid
    L=[]
    R=[]
    for i in range(n1):
        L.append(A[left+i])
    for j in range(n2):
        R.append(A[mid+j])
    L.append(float("inf"))
    R.append(float("inf"))
    i=0
    j=0
    for k in range(left,right):
        if L[i]<=R[j]:
            A[k]=L[i]
            i=i+1
            cnt[0]+=1
        else:
            A[k]=R[j]
            j=j+1
            cnt[0]+=1

def mergeSort(A,left,right):
    if left+1<right:
        mid=(int)((left+right)/2)
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

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

cnt=[0]
mergeSort(S,0,n)
print(*S)
print(cnt[0])


### FIXED CODE ###

global cnt
cnt=0

def merge(A,left,mid,right):
    L=A[left:mid]
    R=A[mid:right]
    L.append(float("inf"))
    R.append(float("inf"))
    
    i=0
    j=0
    for k in range(left,right):
        global cnt
        cnt+=1
        if L[i]<=R[j]:
            A[k]=L[i]
            i=i+1
        else:
            A[k]=R[j]
            j=j+1

def mergeSort(A,left,right):
    if left+1<right:
        mid=(int)((left+right)/2)
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

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

mergeSort(S,0,n)
print(*S)
print(cnt)
### BUGGY CODE ###

H, W, M = list(map(int, input().split()))

targets = set()
row = [0]*H
col = [0]*W

for _ in range(M):
    h, w = list(map(lambda x: int(x) - 1, input().split()))
    row[h] += 1
    col[w] += 1
    targets.add((h, w))

r_max = max(row)
c_max = max(col)
ans = 0
# print([h for h in range(H) if row[h] == r_max])
# print([w for w in range(W) if col[w] == c_max])
for h in [h for h in range(H) if row[h] == r_max]:
    for w in [w for w in range(W) if col[w] == c_max]:
        # print(r_max + c_max - 1 if (h, w) in targets else 0)
        ans = max(ans, r_max + c_max - (1 if (h, w) in targets else 0))
print(ans)



### FIXED CODE ###

H, W, M = list(map(int, input().split()))

targets = set()
row = [0]*H
col = [0]*W

for _ in range(M):
    h, w = list(map(lambda x: int(x) - 1, input().split()))
    row[h] += 1
    col[w] += 1
    targets.add((h, w))

r_max = max(row)
c_max = max(col)
ans = 0

maxed_h = set([h for h in range(H) if row[h] == r_max])
maxed_w = set([w for w in range(W) if col[w] == c_max])
bomb_option_sites_n = len(maxed_h)*len(maxed_w)
targets_on_bomb_option = 0
for th, tw in targets:
    if th in maxed_h and tw in maxed_w:
        targets_on_bomb_option += 1

if bomb_option_sites_n == targets_on_bomb_option:
    print(r_max + c_max - 1)
else:
    print(r_max + c_max)
### BUGGY CODE ###

import itertools

case = 0
while True:
    case += 1
    w_max = int(input())
    if w_max == 0:
        break
    n = int(input())
    t = []
    for i in range(n):
        t.append(list(map(int, input().split(","))))
    v_best = 0
    w_best = 0
    p_all = itertools.product([0,1], repeat=n)
    for p in p_all:
        v = 0
        w = 0
        for i in range(n):
            v += p[i]*t[i][0]
            w += p[i]*t[i][1]
        if v > v_best and w <= w_max:
            v_best = v
            w_best = w
        elif v == v_best and w < w_best:
            v_best = v
            w_best = w
    print("Case ",case,":",sep="")
    print(v_best)
    print(w_best)



### FIXED CODE ###

case = 0
while True:
    case += 1
    w_max = int(input())
    if w_max == 0:
        break
    n = int(input())

    w = [0 for i in range(n)]
    v = [0 for i in range(n)]
    for i in range(n):
        a, b = map(int, input().split(","))
        v[i] = a
        w[i] = b

    dp = [[0 for j in range(w_max + 1)] for i in range(n + 1)]
    for i in range(n)[::-1]:
        for j in range(w_max + 1):
            if j < w[i]:
                dp[i][j] = dp[i + 1][j]
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i])
    print("Case ",case,":",sep="")
    print(max(dp[0]))
    print(dp[0].index(max(dp[0])))
### BUGGY CODE ###

s=int(input())
S=[0] * (len(str(s))+1)
ans=0
for i in range(len(str(s))):
    S[-i-1]=int(str(s)[i:])
for i in range(len(str(s))+1):
    for j in range(i+4, len(str(s))+1):
        if (S[j]-S[i])%2019==0:
            ans+=1
print(ans)

### FIXED CODE ###

s=input()
p=2019
ans=0
M=[0]*p
M[0]=1
tmp=0
for i in range(len(s)):
    tmp+=(int(s[-i-1])*pow(10,i,p))
    tmp%=p
    ans+=M[tmp]
    M[tmp]+=1
print(ans)
### BUGGY CODE ###

import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

h,w,k=map(int,input().split())
R=[]
A=[[0]*w for i in range(h)]
dp=[[[0]*4 for j in range(w)] for i in range(h)]

for i in range(k):
    x,y,v=map(int,input().split())
    x-=1;y-=1
    A[x][y]=v
    dp[x][y][1]=v
    # dp[x][y][2]=v
    # dp[x][y][3]=v;

for i in range(h):
    for j in range(w):
        for k in range(4):
            here=dp[i][j][k]
            if i<h-1:
                dp[i+1][j][0] = max(here,dp[i+1][j][0])
                dp[i+1][j][1] = max(here+A[i+1][j], dp[i+1][j][1])
            if j<w-1:
                dp[i][j+1][k] = max(dp[i][j+1][k], here)
                if k<=2:
                    dp[i][j+1][k+1]= max(dp[i][j+1][k+1],here+ A[i][j+1])
           

print( max(dp[-1][-1]))            


### FIXED CODE ###

import sys

R, C, K = map(int, input().split())
item = [[0] * (C + 1) for _ in range(R + 1)]  # dp配列と合わせるために, 0行目, 0列目を追加している.
for s in sys.stdin.readlines():
    r, c, v = map(int, s.split())
    item[r][c] = v

dp = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]
for i in range(R + 1):
    for j in range(C + 1):
        for k in range(4):
            here = dp[k][i][j]
            # 次の行に移動する場合
            if i + 1 <= R:
                # 移動先のアイテムを取らない場合
                dp[0][i + 1][j] = max(dp[0][i + 1][j], here)
                # 移動先のアイテムを取る場合
                dp[1][i + 1][j] = max(dp[1][i + 1][j], here + item[i + 1][j])
            # 次の列に移動する場合
            if j + 1 <= C:
                # 移動先のアイテムを取らない場合
                dp[k][i][j + 1] = max(dp[k][i][j + 1], here)
                # 現在のkが3未満のときのみ, 移動先のアイテムを取ることが可能
                if k < 3:
                    dp[k + 1][i][j + 1] = max(dp[k + 1][i][j + 1], here + item[i][j + 1])
ans = 0
for k in range(4):
    ans = max(ans, dp[k][-1][-1])
print(ans)
### BUGGY CODE ###

from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)

def debug(var, name="hoge"):
    print(str(type(var)) + name +":" + " = " + repr(var), file=stderr)
    return


def main():
    N, K = list(map(int,input().split()))
    K = bin(K)[2:].zfill(51)
    a = list(map(int,input().split()))
    for i in range(len(a)):
        a[i] = bin(a[i])[2:].zfill(51)
    # memo[決めた桁目(上位から)][K未満 == 1 not == 0] = そのときの最大値
    memo = [0 for __ in range(51)]
    LT = False
    for i in range(51):
        val = 0
        br = 0
        # 1と0の場合,ただしKのi桁目と超えたかにもよって0だけ
        for b in range(2 if LT or K[i] == '1' else 1):
            valtmp = 0
            for n in a:
                valtmp += b ^ int(n[i])
                debug(n[i],str(int(n,2)) + ' ' +str(i))
            if val < valtmp :
                br = b
                val = valtmp
        memo[i] = val
        debug(LT, 'Less than')
        debug(br, 'bin applied')
        LT = br < int(K[i]) or LT


    p = 1
    ans = 0
    for i in range(50,-1,-1):
        ans += p*memo[i]
        p *= 2
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)

def debug(var, name="hoge"):
    print(str(type(var)) + name +":" + " = " + repr(var), file=stderr)
    return


def main():
    N, K = list(map(int,input().split()))
    K = bin(K)[2:].zfill(51)
    a = list(map(int,input().split()))
    for i in range(len(a)):
        a[i] = bin(a[i])[2:].zfill(51)
    # memo[決めた桁目(上位から)][K未満 == 1 not == 0] = そのときの最大値
    memo = [0 for __ in range(51)]
    LT = False
    for i in range(51):
        val = 0
        br = 0
        # 1と0の場合,ただしKのi桁目と超えたかにもよって0だけ
        for b in range(2 if LT or K[i] == '1' else 1):
            valtmp = 0
            for n in a:
                valtmp += b ^ int(n[i])
            if val < valtmp :
                br = b
                val = valtmp
        memo[i] = val
        LT = br < int(K[i]) or LT


    p = 1
    ans = 0
    for i in range(50,-1,-1):
        ans += p*memo[i]
        p *= 2
    print(ans)


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

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

n = input()

N = 10

child_data = [[1]*len(n)]
for j in range(1, len(n)+1):
    child_fin = [0]*len(n)
    for i in range(len(n)):
        if n[i] == "L":
            child_fin[i-1] += child_data[j-1][i]
        else:
            child_fin[i+1] += child_data[j-1][i]
    child_data.append(child_fin)
    if child_fin in child_data[:-1]:
        child_last = child_data[-(j%2+1)]

output = " ".join(map(str, child_last))
print(output)

### FIXED CODE ###

def main():
    s = input()

    spl = s.split("LR")

    for i, e in enumerate(spl):
        spl[i] = "R" + spl[i] + "L"

    spl[0] = spl[0][1:]
    spl[-1] = spl[-1][:-1]

    ans = []
    for es in spl:
        rl_i = es.find("RL")
        l = len(es)
        q, r = divmod(l, 2)
        for i, e in enumerate(es):
            if i == rl_i or i == rl_i + 1:
                tmp = q + r * ((i + 1) % 2)
                ans.append(tmp)
            else:
                ans.append(0)

    print(*ans)


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

from sys import stdin
input = stdin.readline

n = int(input())
a = [int(x) for x in input().split()]
b = [0] * 1000001

for x in a:
    for y in range(x, 1000001, x):
        b[y] += 1

cnt = 0

for x in a:
    if b[x] == 1:
        cnt += 1

print(cnt)

### FIXED CODE ###

from sys import stdin
input = stdin.readline

n = int(input())
a = [int(x) for x in input().split()]
b = [0] * 1000001
chk = [0] * 1000001
s = set(a)

for x in a:
    chk[x] += 1

for x in s:
    for y in range(x, 1000001, x):
        b[y] += 1

cnt = 0

for x in s:
    if b[x] == 1 and chk[x] == 1:
        cnt += 1

print(cnt)
### BUGGY CODE ###

def isPrime(x):
    if x==2:
        return True
    if x<2 or x%2==0:
        return False
    if pow(2,x-1,x)==1:
        return True
    else:
        return False
while 1:
    try:
        n=input()
        ct=1
        if n==2:
            print(1)
        else:
            for i in xrange(3,n+1,2):
                if isPrime(i):
                    ct+=1
            print(ct)
    except:
        break

### FIXED CODE ###

def sieve(n):
    p=0
    prime=[0]*n
    is_prime=[0]*(n+1)
    for i in xrange(n+1):
        is_prime[i]=True
    is_prime[0]=is_prime[1]=False
    for i in xrange(2,n+1):
        if is_prime[i]:
            p+=1
            prime[p]=i
            for j in xrange(2*i,n+1,i):
                is_prime[j]=False
    return p
while 1:
    try:
        n=input()
        print(sieve(n))
    except:
        break