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

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

if B <= N:
    x = B - 1
    ans = (A*x)//B-A*(x//B)
if B > N:
    ans = 0
    for x in range(1, N+1):
        ans = max(ans, (A*x)//B-A*(x//B))
print(ans)

### FIXED CODE ###

A, B, N = map(int, input().split())
if N >= B:
    x = B - 1
else:
    x = N
print( (A*x//B) - A*(x//B) )
### BUGGY CODE ###

mod = 10**9+7
N = int(input())
A = list(map(int,input().split()))
tmp = 0
for i in range(61):
    tmp_0 = 0
    for j in range(N):
        if ((A[j] >> i) & 1) == 0:
            tmp_0 += 1
    tmp += ((tmp_0)*(N - tmp_0)*(2**i)) % mod
print(tmp % mod)

### FIXED CODE ###

import numpy as np
mod = 10**9+7
N = int(input())
A = list(map(int,input().split()))
A = np.array(A, dtype = np.int64)
tmp = 0
for i in range(61):
    tmp_1 = np.count_nonzero(A & 1)
    tmp += ((tmp_1)*(N - tmp_1)*(2**i)) % mod
    A = A >> 1
print(tmp % mod)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**10
 
h, n = [int(item) for item in input().split()]
MAX_LEN = h + 10**4 + 1
dp = [INF] * MAX_LEN
dp[0] = 0
for i in range(n):
    v, w = map(int, input().split())
    for j in range(h+1):
        if dp[j] != INF and dp[j] + w < dp[j+v]:
            dp[j+v] = dp[j] + w
ans = min(dp[h:])
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 - 2
    dp = [INF] * MAX_LEN
    dp[0] = 0
    vw = []
    for _ in range(n):
        v, w = map(int, input().split())
        vw.append((v, w))
    vw.sort(reverse=True, key=lambda x:x[0])
    for v, w in vw:
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

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

from bisect import bisect_left
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
BC = sorted(BC,key= lambda x: x[1],reverse=True)
A.sort()
for i in range(M):
    if BC[i][1]<A[0]:
        break
    B= BC[i][0]
    C = BC[i][1]
    b = bisect_left(A,C)
    if B>=b:
        A[:b] = [C for _ in range(b)]
    else:
        A[:B] = [C for _ in range(B)]
    A.sort()
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
BC = sorted(BC,key= lambda x: x[1],reverse=True)
A.sort()
n = 0
i = 0
m = 0
while A[i]<BC[n][1]:
    A[i] = BC[n][1]
    m = m+1
    if m >=BC[n][0]:
        m = 0
        n = n+1
    i += 1
    if n==M:
      break
    if i == N:
      break
print(sum(A))
### BUGGY CODE ###

n=int(input())
c=list(map(int,input().split()))
c.sort(reverse=1)
d=2**(n-2)
m=10**9+7
ans=0
k=1
for x in c:
  x=int(x%m)
  ans+=x*(k+1)*d
  ans%=m
  k+=1
ans=(int(ans)%m*(2**n))%m

print(int(ans))

### FIXED CODE ###

n=int(input())
c=list(map(int,input().split()))
c.sort(reverse=1)
m=10**9+7
d=(2**(n-2))%m
ans=0
k=2
for x in c:
  x=int(x%m)
  ans+=(x*k*d)%m
  k+=1
ans=(int(ans)%m*d*4)%m

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

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

resultCount = 0
for i in range(N):
    isMitasu = True
    for j in range(i):
        if P[i] > P[j]:
            isMitasu = False
            break
    if isMitasu:
        resultCount += 1
print(resultCount)

### FIXED CODE ###

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


# 最小値更新して越えてたらアウト
resultCount = 0
minNum = P[0]
for i in range(N):
    isMitasu = True
    if i != 0:
        if P[i] > minNum:
            isMitasu = False
        else:
            # 最小値更新
            minNum = P[i]
    if isMitasu:
        resultCount += 1
print(resultCount)
### BUGGY CODE ###

import sys
import math

stdin = sys.stdin

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

a, b = nm()

n = math.gcd(a,b)

m = int(n**(1/2))


count = 1 # 1
for i in range(2, n+1):
    if n%i ==0:
        count +=1
        while n%i == 0:
            n = n/i
    if n ==1:
        break

print(count)


### FIXED CODE ###

import sys
import math

stdin = sys.stdin

nm = lambda: map(int, stdin.readline().split())

a, b = nm()

n = math.gcd(a,b)

count = 1 # 1
for i in range(2, int(n**(1/2))+1):
    if n%i ==0:
        count +=1
        while n%i == 0:
            n = n/i
    if n ==1:
        break
if n != 1:
    count += 1

print(count)
### BUGGY CODE ###

import itertools
import math
import fractions
import functools
import copy
from collections import deque
from functools import reduce
from decimal import Decimal


def main():
    n = int(input())


    def f(i):
        l = []
        for a in range(1, math.floor(math.sqrt(i))):
            l.append(a)
        l_list = list(itertools.combinations_with_replacement(l, 3))
        count = 0
        for j in range(len(l_list)):
            x = l_list[j][0]
            y = l_list[j][1]
            z = l_list[j][2]
            ans = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if ans == i and x == y and y == z:
                count += 1
            elif ans == i:
                count += 3
            if ans > i*2:
                break
        return count

    for i in range(1, n+1):
        count = f(i)
        if count != 0:
            print(count)
        else:
            print(0)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import itertools
import math
import fractions
import functools
import copy
from collections import deque
from functools import reduce
from decimal import Decimal


def main():
    n = int(input())
    l = [0]*(n+1)
    for x in range(1,101):
        for y in range(1,101):
            for z in range(1,101):
                temp = x**2 + y**2 + z**2 + x*y + y*z + z*x
                if temp <= n:
                    l[temp] += 1

    for i in range(1, n+1):
        print(l[i])


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

n = int(input())
l = list(map(int, input().split()))
sort_l = sorted(l)
count = 0
for i in range(n-2):
    for j in range(i+1, n-1):        
        for k in range(j+1, n):
            two_line = sort_l[i] + sort_l[j]
            one_line = sort_l[k]
            if two_line > one_line:
                count += 1

print(count)



### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int, input().split()))
sort_l = sorted(l)
count = 0

for a in range(n):
    for b in range(a+1, n):
        c = bisect.bisect_left(sort_l, sort_l[a] + sort_l[b])
        if c > b:
            count += c - b -1
        else:
            pass     
        

print(count)
### BUGGY CODE ###

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a

N = int(input())
A = list(map(int, input().split()))
if N == 1:
    print('1')
else:
    gcd = xgcd(A[0],A[1])
    lcm = (A[0]*A[1]) // gcd
    for i in range(2,N):
        gcd = xgcd(lcm,A[i])
        lcm = (lcm * A[i]) // gcd
    ans = 0
    b = [lcm // x for x in A]
    for x in b:
        ans = (ans + x) % 1000000007
    print(ans)

### FIXED CODE ###

from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
if N == 1:
    print('1')
else:
    g = gcd(A[0],A[1])
    lcm = (A[0]*A[1]) // g
    for x in A[2:]:
        lcm = (lcm * x) // gcd(lcm,x)
    print(sum((lcm//x) for x in A)%1000000007)
### BUGGY CODE ###

MOD = 10**9+7

def start(a):
    num = 0
    for i in range(1, a):
        num += i
    return num

def end(m, b):
    num = 0
    for i in range(n, n-b, -1):
        num += i
    return num

n, k = map(int, input().split())
ans = 0
for i in range(k, n+2):
    s = start(i)
    e = end(n, i)
    cnt = e-s+1
    ans = ans + cnt
    ans %= MOD
print(ans)

### FIXED CODE ###

MOD = 10**9+7


def end(b):
    num = 0
    for i in range(n, n-b, -1):
        num += i
    return num

n, k = map(int, input().split())
ans = 0
for i in range(k, n+2):
    s = (i-1) * i // 2
    e = (2*n-i+1) * i // 2
    #print(s, e)
    cnt = e-s+1
    ans = ans + cnt
    ans %= MOD
print(ans)
### BUGGY CODE ###

def gdc(x,y):
  if x%y==0:
    return y
  return gdc(y, x%y)

def main():
  K = int(input())
  total = 0

  for a in range(K):
    for b in range(K):
      for c in range(K):
        total += gdc(c+1, gdc(b+1, a+1))
  print(total)
  
if __name__ == '__main__':
    main()

### FIXED CODE ###

K = int(input())
total = 0

def gdc(x,y):
  if x%y==0:
    return y
  return gdc(y, x%y)

for a in range(K):
  for b in range(a,K):
    for c in range(b,K):
      if a==b and b==c:
        total += gdc(c+1, gdc(b+1, a+1))
      elif a==b or b==c or a==c:
        total += 3*gdc(c+1, gdc(b+1, a+1))
      else:
        total += 6*gdc(c+1, gdc(b+1, a+1))
print(total)
### BUGGY CODE ###

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

### FIXED CODE ###

n = int(input())
d,x = map(int,input().split())
count = x
a = [int(input()) for i in range(n)]
for i in range(n):
  j = 0
  while j * a[i] + 1 <= d:
    count += 1
    j += 1
print(count)
### BUGGY CODE ###

N = int(input())
s = [input() for _ in range(N)]

import collections
c = collections.Counter(s)

keys = [k for k, v in c.items() if  v == max(c.values())]
[print(sorted(keys)[i]) for i in range(len(keys))]

### FIXED CODE ###

import collections
N = int(input())
S = [input() for _ in range(N)]

if len(S) == len(set(S)):
  ans = S
else:
  ans = []
  c = collections.Counter(S)
  c_common = c.most_common()
  max_vote = c_common[0][1]
  for k in range(len(set(S))):
    if c_common[k][1]== max_vote:
      ans.append(c_common[k][0])
    else:
      break
[print(a) for a in sorted(ans)]
### BUGGY CODE ###

# coding: utf-8
import os
import time
import re
import math


def main():
    N=int(input())
    A=[int(input()) for  a in range(N)] 
    #start=time.time();
    totalList=[]
    for a in range(1<<N):
        bit=[]
        for b in range(N):
            if (a & (1<<b))>0:
                bit.insert(0,1)
            else:
                bit.insert(0,0)
        total=0
        for b in range(N):
                total+=A[b]*bit[b]
        totalList.append(total)
    totalList.sort(key=lambda x: -x)
    ans=0
    for a in totalList:
        if not a%10==0:
            ans=a
            break
    print(ans)

    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#


main()


### FIXED CODE ###

# coding: utf-8
import time
import re
import math

def main():
    global N,A,memo
    N=int(input())
    A=[int(input()) for  a in range(N)] 
    if sum(A)%10==0:
        nm0=[]
        for a in A:
            if not a%10==0:
                nm0.append(a)
        if len(nm0)==0:
            print(0)
        else:
            print(sum(A)-min(nm0))

    else:
        print(sum(A))

main()
### BUGGY CODE ###

import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret *= 3

memo = np.full(((n+1), (n * max(aa) + 1), 2), -1, dtype=np.int32)
def dfs(i, c):
    if 0 <= memo[i, c, 0]:
        return memo[i, c]

    if i == n:
        memo[i, c, 0] = 3 if total <= (2 * c) else 0
        memo[i, c, 1] = 3 if total == (2 * c) else 0
        return memo[i, c]

    v0, v1 = dfs(i + 1, c)
    v2, v3 = dfs(i + 1, c + aa[i])

    acc0 = (v0 + v0) % 998244353
    acc0 = (acc0 + v2) % 998244353
    memo[i, c, 0] = acc0

    memo[i, c, 1] = (v1 + v3) % 998244353
    return memo[i, c]

a, b = dfs(0, 0)
ret = (ret - a + b) % 998244353
print(ret)

### FIXED CODE ###

import sys

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret *= 3


L = (n * max(aa) + 1)
memo = [-1] * ((n+1) * L * 2)
def dfs(i, c):
    key = (i * L * 2) + 2 * c
    if 0 <= memo[key]:
        return memo[key: key+2]

    if i == n:
        memo[key + 0] = 3 if total <= (2 * c) else 0
        memo[key + 1] = 3 if total == (2 * c) else 0
        return memo[key: key + 2]

    v0 = dfs(i + 1, c)
    v1 = dfs(i + 1, c + aa[i])

    memo[key + 0] = (2 * v0[0] + v1[0]) % 998244353
    memo[key + 1] = (v0[1] + v1[1]) % 998244353
    return memo[key: key + 2]

a, b = dfs(0, 0)
ret = (ret - a + b) % 998244353
print(ret)
### BUGGY CODE ###

s=input()
q=int(input())
ok=1
for i in range(q):
  query=list(input().split())
  if query[0]=='1':
    ok=(ok+1)%2
  else:
    f,c=query[1],query[2]
    if ok:
      if f=='1':
        s=c+s
      else:
        s+=c
    else:
      if f=='1':
        s=s+c
      else:
        s=c+s
if ok:
  print(s)
else:
  print(s[::-1])

### FIXED CODE ###

from collections import deque
def main():
  s=deque(list(input()))
  q=int(input())
  ok=1
  for i in range(q):
    query=list(input().split())
    if query[0]=='1':
      ok=(ok+1)%2
    else:
      f,c=query[1],query[2]
      if ok:
        if f=='1':
          s.appendleft(c)
        else:
          s.append(c)
      else:
        if f=='1':
          s.append(c)
        else:
          s.appendleft(c)
  s=list(s)
  if ok:
    print(''.join(s))
  else:
    print(''.join(s[::-1]))
if __name__=='__main__':
  main()
### BUGGY CODE ###

# #bin()やformat(数字 ,"b")を使うとstr型になる
# #bin()とformat(数字 ,"#b")は同意

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7

for i in range(N): A[i] = format(A[i], "#b") #ここで全て60ビットの二進数に変換

sum = 0
c0 = [0]*60
c1 = [0]*60
for i in range(N):
    for j in range(60):
        if A[i][-(j+1)] == "0": #str型であることに注意！
            c0[j] += 1
        elif A[i][-(j+1)] == "1":
            c1[j] += 1
        else:
            break

for i in range(60):
    if c1[i] > 0:
        c0[i] = N - c1[i] 
    sum += (c0[i] * c1[i]) << i

print(sum%mod)


# N = int(input())
# A = list(map(int, input().split()))

# for i in range(N): A[i] = format(A[i], "060b") #ここで全て60ビットの二進数に変換

# mod = 10**9+7

# sum = 0
# for i in range(1,61):
#     count0 = 0
#     count1 = 0
#     for j in range(N):
#         if A[j][-i] == "0": #str型であることに注意！
#             count0 += 1
#         else:
#             count1 += 1 
#     sum += (count0 * count1) << (i-1) #左シフトだが，2**(i-1)でもOK (処理速度変わらない)
# print(sum%mod)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
xorsum = 0
for i in range(60):
  c1 = sum([1 for a in A if (a >> i) & 1]) #
  xorsum += (c1*(N-c1)*(1<<i))
  xorsum = xorsum%mod
print(xorsum%mod)
### BUGGY CODE ###

n, m = map(int, input().split())
arr = []
for _ in range(n):
    a, b = map(int, input().split())
    arr.append((a, b))


arr.sort(key=lambda x: x[0])
arr.sort(key=lambda x: x[1], reverse=True)

res = 0
for m_i in range(1, m + 1):
    for x in range(len(arr)):
        a, b = arr[x]
        if a <= m_i:
            res += b
            del arr[x]
            break
print(res)


### FIXED CODE ###

from heapq import heappush, heappop
n, m = map(int, input().split())

in_dict = {}
for _ in range(n):
    a, b = map(int, input().split())
    in_dict[a] = in_dict.get(a, [])
    in_dict[a].append(b)

heap = []
res = 0
for m_i in range(1, m + 1):
    for i in in_dict.get(m_i, []):
        heappush(heap, -i)
    if heap:
        res += -heappop(heap)

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

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

Al = sorted(A,reverse=True)[:K]
Bl = sorted(B,reverse=True)[:K]
Cl = sorted(C,reverse=True)[:K]

result = []
for i in range(len(Al)):
    for j in range(len(Bl)):
        for k in range(len(Cl)):
            result.append(Al[i]+Bl[j]+Cl[k])

result.sort(reverse=True)

for i in range(K):
    print(result[i])


### FIXED CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
e=[]
for ai in a:
    for bi in b:
        e.append(ai+bi)
e.sort(reverse=True)
e=e[:k]
ans=[]
for ci in c:
    for ei in e:
        ans.append(ci+ei)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

def div(n):
  ret=[]
  for i in range(1,int(n**0.5)+1):
    if n%i==0:
      ret.append(i)
      if i!=n//i:
        ret.append(n//i)
  return ret

n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
s=sum(arr)
ans=1
d=div(s)
for val in d:
  arr=sorted(arr,key=lambda x:x%val)
  for i in range(n-1):
    pcnt=0
    ncnt=0
    for j in range(n):
      if j<=i:
        ncnt+=arr[j]%val
      else:
        pcnt+=(val-arr[j]%val)
    if ncnt!=pcnt:
      continue
    else:
      if pcnt<=k:
        ans=max(ans,val)
print(ans)

### FIXED CODE ###

def div(n):
  ret=[]
  for i in range(1,int(n**0.5)+1):
    if n%i==0:
      ret.append(i)
      if i!=n//i:
        ret.append(n//i)
  return ret

n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
s=sum(arr)
ans=1
d=div(s)
for val in d:
  arr=sorted(arr,key=lambda x:x%val)
  parr=[]
  narr=[]
  for num in arr:
    narr.append(num%val)
    parr.append(val-num%val)
  for i in range(n-1):
    parr[i+1]+=parr[i]
    narr[i+1]+=narr[i]
  for i in range(n-1):
    ncnt=narr[i]
    pcnt=parr[-1]-parr[i]
    if ncnt!=pcnt:
      continue
    else:
      if pcnt<=k:
        ans=max(ans,val)
print(ans)
### BUGGY CODE ###

import sys
nm = input().split()
n = int(nm[0])
m = int(nm[1])
lr = [input().split() for i in range(m)]
l = [int(lr[i][0]) for i in range(m)]
r = [int(lr[i][1]) for i in range(m)]

card = [i for i in range(n + 1)]
if m == 1:
  print(len(card[l[0]:r[0]]) + 1)
  sys.exit()
card2 = []
card_duplicate = []
for i in range(m):
  #card2 = card_duplicate
  card2.extend(card[l[i]-1:r[i]])

card_duplicate = [x for x in set(card2) if card2.count(x) == m]

print(len(card_duplicate))

### FIXED CODE ###

nm = input().split()
n = int(nm[0])
m = int(nm[1])
lr = [input().split() for i in range(m)]
l = [int(lr[i][0]) for i in range(m)]
r = [int(lr[i][1]) for i in range(m)]
a = min(r) -max(l) + 1
if a >= 0:
  print(a)
else:
  print(0)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class Segtree():
    def __init__(self, aa):
        self.n = n = len(aa)
        self.tree_width = tree_width = 1 << (n - 1).bit_length()
        self.tree = [0] * (tree_width * 2 - 1)
        self.tree[tree_width-1:tree_width-1+n]=aa
        for u in range(tree_width - 2, -1, -1):
            self.tree[u] = self.tree[u * 2 + 1]|self.tree[u * 2 + 2]

    def get(self, l, r, seg_i=0, segL=0, segR=-1):
        if segR == -1: segR = self.tree_width
        if r <= segL or segR <= l: return 0
        if l <= segL and segR <= r: return self.tree[seg_i]
        segM = (segL + segR) // 2
        ret0 = self.get(l, r, seg_i * 2 + 1, segL, segM)
        ret1 = self.get(l, r, seg_i * 2 + 2, segM, segR)
        return ret0|ret1

n,q=MI()
cc=MI()
aa=[1<<c for c in cc]
st=Segtree(aa)
for _ in range(q):
    l,r=MI()
    print(bin(st.get(l-1,r)).count("1"))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class BitSum:
    def __init__(self, n):
        self.n = n + 1
        self.table = [0] * self.n

    def add(self, i, x):
        i += 1
        while i < self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

n,q=MI()
cc=LI()
lri=[]
mx=500005
#mx=10
for i in range(q):
    l,r=MI()
    l-=1
    lri.append((l,r-1,i))

lri.sort(key=lambda x:x[1])

#print(lri)
last=[-1]*mx
st=BitSum(mx)
ans=[0]*q
now=0
for l,r,i in lri:
    for j in range(now,r+1):
        c=cc[j]
        pre=last[c]
        if pre!=-1:st.add(pre,-1)
        last[c]=j
        st.add(j,1)
    #print(l,r,st.tree,last)
    now=r+1
    ans[i]=st.sum(r)-st.sum(l-1)
print(*ans,sep="\n")
### BUGGY CODE ###

import numpy as np

N, W = map(int, raw_input().split())
dp = np.zeros(W+1)

for i in range(N):
    w, v = map(int, raw_input().split())
    for j in range(W, w-1, -1):
        x = dp[j-w]+v
        if x > dp[j]:
            dp[j] = x


print int(dp[-1])



### FIXED CODE ###

def main():

    N, W = map(int, raw_input().split())
    dp = [0]*(W+1)
 
    for i in xrange(N):
        w, v = map(int, raw_input().split())
        for j in xrange(W, w-1, -1):
            x = dp[j-w] + v
            if x > dp[j]:
                dp[j] = x
 
    print dp[-1]

main()
### BUGGY CODE ###

L,R=map(int,input().split())
c=2019
for i in range(L,R+1):
    for j in range(i+1,R+1):
        a=i*j
        b=a%2019
        if c>b:
            c=b
    if c==0:
        break
print(c)

### FIXED CODE ###

L,R=map(int,input().split())
c=2019
z=0
for i in range(L,R+1):
    for j in range(i+1,R+1):
        a=i*j
        b=a%2019
        if c>b:
            c=b
        if c==0:
            z=1
            break
    if z==1:
        break
print(c)
### BUGGY CODE ###

from functools import cmp_to_key
n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
d.sort(key = cmp_to_key(lambda x, y: y[1] / y[0] - x[1] / x[0]))
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys())) # sort しないと品物iを複数回ナップサックに詰める可能性がある
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        for k in list(t.keys()):
          if k < nw and t[k] <= nv:
            del t[k]
        t[nw] = nv
    else:
      Flag = False
      for k in t:
        if nw < k and nv <= t[k]:
          Flag = True
          break
      if Flag:
        continue
      for k in list(t.keys()):
        if k < nw and t[k] <= nv:
          del t[k]
      t[nw] = nv
        
print(max(t.values()))


### FIXED CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys()))
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))
### BUGGY CODE ###


N, M = map(int, input().split())
bridge = [ list(map(int, input().split())) for _ in range(M)]

cut_count = 0
while True:
    summ = [ 0 for _ in range(N)]
    for b in bridge:
        for i in range(N):
            if (b[0] - 1) <= i < (b[1] - 1):
                summ[i] += 1
#     print(summ, bridge)
    maxx = max(summ)
    if maxx < 2:
        print(str(len(bridge) + cut_count))
        break
    else:
        cut_count += 1
        ind = summ.index(maxx)
        new_bridge = []
        for b in bridge:
            for i in range(N):
                if (b[0] - 1) <= ind < (b[1] - 1):
                    pass
                else:
                    new_bridge.append(b)
                    break
        bridge = new_bridge
        

### FIXED CODE ###


N, M = map(int, input().split())
bridge = [ list(map(int, input().split())) for _ in range(M)]

bridge.sort(key=lambda x:x[1])

cuts = [bridge[0][1]]
for b in bridge[1:]:
    cut = cuts[-1]
    if b[0]< cut <= b[1]:
        continue
    cuts.append(b[1])

# print(cuts)
print(len(cuts))