Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Chef has a sequence A with length N and a line given by the equation y(x) = k · x + b. Let us say that an element A_{j} is reachable from another element A_{i} if the point (A_{i}, A_{j}) is lying above or on the line y(x), i.e. if A_{j} ≥  k · A_{i} + b.

Consider an arbitrary subsequence of A; let's denote it by B. Subsequence B is called good if its elements can be reordered in such a way that for each valid i, B_{i+1} is reachable from B_{i}.

Chef asked you to compute the maximum possible length of a good subsequence. Can you help him?

------ Input ------ 

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains three space-separated integers N, k and b.
The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N}.

------ Output ------ 

For each test case, print a single line containing one integer — the length of the longest good subsequence of A.

------ Constraints ------ 

$1 ≤ T ≤ 5000$
$1 ≤ N ≤ 100000$
$0 ≤ k, b ≤ 10^{9}$
$0 ≤ A_{i} ≤ 10^{9} for each valid i$
$1 ≤ sum of N over all test cases ≤ 200000$

----- Sample Input 1 ------ 
1
5 4 1
100 2 4 17 8
----- Sample Output 1 ------ 
3
----- explanation 1 ------ 
Example case 1: We can choose the subsequence (100, 4, 17) and reorder it to get the sequence (4, 17, 100). In this sequence, 17 is reachable from 4 because 4 · 4 + 1 = 17 ? 17 and 100 is reachable from 17 because 4 · 17 + 1 = 69 ? 100. Hence, (100, 4, 17) is a good subsequence; there is no good subsequence of A with length 4 or more, so the answer is 3.

Source: codechef | Difficulty: HARD
Tags: Sorting

Range queries

Greedy algorithms

Complete search

Dynamic programming

Segment trees revisited

Data structures


Solutions:
def lis(arr):
	if len(arr) == 0:
		return 0
	l = [arr[0]]
	for element in arr[1:]:
		(left, right) = (-1, len(l))
		while right - left > 1:
			mid = (left + right) // 2
			if k * l[mid] + b <= element:
				left = mid
			else:
				right = mid
		if right == len(l):
			l.append(element)
		else:
			l[right] = min(l[right], element)
	return len(l)
for _ in range(int(input())):
	(N, k, b) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	print(lis(a))


def main():
	T = int(input().strip())
	for i in range(T):
		tmp = list(map(int, input().strip().split()))
		Len = tmp[0]
		k = tmp[1]
		b = tmp[2]
		nums = list(map(int, input().strip().split()))
		nums.sort()
		tmp = -1
		tmp_count = 0
		for j in range(0, Len):
			if tmp <= nums[j]:
				tmp = nums[j] * k + b
				tmp_count += 1
		print(tmp_count)
main()


for _ in range(int(input())):
	(n, k, b) = map(int, input().split())
	s = list(map(int, input().split()))
	s.sort()
	max_len = 1
	l = 0
	r = 1
	while r < n:
		if s[r] >= k * s[l] + b:
			max_len += 1
			l = r
		r += 1
	print(max_len)


def solve():
	(n, k, b) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	A.sort()
	(count, prev) = (1, A[0])
	for i in range(1, n):
		if A[i] >= k * prev + b:
			count += 1
			prev = A[i]
	return count
t = int(input())
while t:
	print(solve())
	t -= 1


T = int(input())
for _ in range(T):
	(N, k, b) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	pre = [0 for i in range(N)]
	for i in range(N):
		pre[i] = k * A[i] + b
	ans = 1
	m = pre[0]
	for i in range(1, N):
		if A[i] >= m:
			ans += 1
			m = pre[i]
	print(ans)


def solve(k, b, l):
	l.sort()
	pairs = 0
	y = k * l[0] + b
	count = 1
	for i in range(1, len(l)):
		if l[i] >= y:
			y = k * l[i] + b
			count += 1
	return count

def isthere(y, l):
	for i in range(0, len(l)):
		if l[i] >= y:
			return i

def bsearch(low, high, key, l):
	if low == high:
		if l[low] >= key:
			return low
		else:
			return -1
	mid = (low + high) // 2
	if key >= l[low] and key <= l[mid]:
		bsearch(low, mid, l, key)
	else:
		bsearch(mid, high, key, l)
n = int(input())
while n:
	(num, k, b) = map(int, input().split())
	l = list(map(int, input().split()))
	print(solve(k, b, l))
	n = n - 1


def solve(k, b, l):
	l.sort()
	pairs = 0
	y = k * l[0] + b
	count = 1
	for i in range(1, len(l)):
		if l[i] >= y:
			y = k * l[i] + b
			count += 1
	return count
n = int(input())
while n:
	(num, k, b) = map(int, input().split())
	l = list(map(int, input().split()))
	print(solve(k, b, l))
	n = n - 1


for _ in range(int(input())):
	(n, k, b) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	arr.sort()
	ans = 1
	for i in range(1, len(arr)):
		if arr[i] >= arr[i - 1] * k + b:
			ans += 1
		else:
			arr[i] = arr[i - 1]
	print(ans)


for i in range(int(input())):
	(n, k, b) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	c = k * A[0] + b
	x = 1
	for i in range(1, n):
		if A[i] >= c:
			x += 1
			c = k * A[i] + b
	print(x)


mapInput = lambda : map(int, input().split())
listInput = lambda : list(mapInput())
for _ in range(int(input())):
	(n, k, b) = mapInput()
	a = listInput()
	a.sort()
	cnt = 1
	i = 1
	l = a[0]
	while i < n:
		if k * l + b <= a[i]:
			l = a[i]
			cnt += 1
		i += 1
	print(cnt)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	(n, k, b) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	l.sort()
	ans = 1
	cur_element = l[0]
	for i in range(1, n):
		next_el = cur_element * k + b
		if l[i] >= next_el:
			cur_element = l[i]
			ans += 1
	print(ans)


t = int(input())
for i in range(t):
	(n, j, b) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	c = l[0] * j + b
	x = 1
	for k in range(1, n):
		if l[k] >= c:
			x += 1
			c = l[k] * j + b
	print(x)


from sys import stdin
input = stdin.readline
from bisect import bisect_left as bl

def f(a, k, b):
	a.sort()
	ans = 0
	i = 0
	while i < len(a):
		ans += 1
		ll = bl(a, k * a[i] + b, lo=i + 1)
		i = ll
	return ans
for _ in range(int(input())):
	(n, k, b) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	print(f(a, k, b))


tc = int(input())
while tc > 0:
	(n, j, b) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	c = arr[0] * j + b
	x = 1
	for i in range(1, n):
		if arr[i] >= c:
			x += 1
			c = arr[i] * j + b
	print(x)
	tc -= 1


t = int(input())
for i in range(t):
	(n, k, b) = map(int, input().split())
	l1 = [int(i) for i in input().split()]
	if n == 1:
		print(1)
	else:
		l1.sort()
		(ans, req) = (0, 0)
		for i in l1:
			if i >= req:
				ans += 1
				req = i * k + b
		print(ans)


t = int(input())
for i in range(t):
	(n, k, b) = map(int, input().split())
	lis = list(map(int, input().split()))
	lis.sort()
	j = 0
	c = 0
	l = len(lis)
	while j < l:
		elem = lis[j]
		c += 1
		j += 1
		while j < l:
			if lis[j] < elem * k + b:
				j += 1
			else:
				break
	print(c)


t = int(input())
for _ in range(t):
	(n, k, b) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	arr.sort()
	dp = [1]
	count = 1
	temp = arr[0]
	for j in range(1, n):
		calc = k * temp + b
		if arr[j] >= calc:
			temp = arr[j]
			count += 1
	dp.append(count)
	print(max(dp))


t = int(input())
for _ in range(t):
	(n, k, x) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	ans = 1
	c = l[0] * k + x
	for i in range(1, n):
		if l[i] >= c:
			c = l[i] * k + x
			ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, k, b) = map(int, input().split())
	arr = list(map(int, input().split()))
	out = []
	arr.sort()
	for i in range(len(arr)):
		t = arr[i] * k + b
		out.append(t)
	count = 1
	z = out[0]
	for i in range(1, len(arr)):
		if arr[i] >= z:
			z = out[i]
			count += 1
	print(count)


t = int(input())
while t > 0:
	inp = input()
	(n, k, b) = (int(x) for x in inp.split())
	inp2 = input()
	arr = list(map(int, inp2.split()))
	arr.sort()
	resultArr = [arr[0]]
	for j in range(1, n):
		if resultArr[-1] * k + b <= arr[j]:
			resultArr.append(arr[j])
	print(len(resultArr))
	t -= 1


t = int(input())
for i in range(t):
	(n, k, b) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	z = l[0] * k + b
	count = 1
	for i in range(1, n):
		if l[i] >= z:
			count += 1
			z = l[i] * k + b
	print(count)


tt = int(input())
while tt:
	(n, b, a) = map(int, input().split())
	l = [int(s) for s in input().split()]
	l.sort()
	cnt = 1
	re = l[0] * b + a
	for i in range(1, len(l)):
		if re <= l[i]:
			cnt += 1
			re = l[i] * b + a
	print(cnt)
	tt -= 1


def main():
	t = int(input())
	for z in range(t):
		N_k_b = [int(x) for x in input().split()]
		li = [int(x) for x in input().split()]
		li.sort()
		count = 0
		value = li[0]
		for i in range(N_k_b[0]):
			if li[i] >= value:
				count += 1
				value = N_k_b[1] * li[i] + N_k_b[2]
		print(count)
main()


t = int(input())
while t > 0:
	(n, k, b) = map(int, input().split())
	x = list(map(int, input().split()))
	x.sort()
	v = k * x[0] + b
	c = 1
	for i in range(1, n):
		if v <= x[i]:
			v = k * x[i] + b
			c += 1
	print(c)
	t -= 1


t = int(input())
for test in range(t):
	(n, a, b) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr1 = sorted(arr)
	arr3 = []
	for i in arr1:
		arr3.append(i * a + b)
	j = len(arr3) - 1
	count = 0
	for i in range(len(arr1) - 2, -1, -1):
		if arr3[i] <= arr1[j]:
			j = i
			count += 1
	print(count + 1)


t = int(input())
for i in range(t):
	(N, k, b) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	a = sorted(a, reverse=True)
	m = 0
	count = 1
	for i in range(1, N):
		if a[m] >= k * a[i] + b:
			m = i
			count += 1
	print(count)


t = int(input())
for i in range(t):
	(N, k, b) = list(map(int, input().split()))
	a = [int(x) for x in input().split()]
	a = sorted(a, reverse=True)
	l = len(a)
	m = 0
	count = 1
	for i in range(1, l):
		if a[m] >= k * a[i] + b:
			m = i
			count += 1
	print(count)


t = int(input())
for _ in range(t):
	(n, k, b) = [int(x) for x in input().strip().split(' ')]
	arr = [int(x) for x in input().strip().split(' ')]
	arr = sorted(arr)
	count = 1
	mul = arr[0] * k + b
	for i in range(1, n):
		if arr[i] >= mul:
			count += 1
			mul = arr[i] * k + b
	print(count)


t = int(input())
while t:
	t = t - 1
	(n, k, b) = input().split()
	y = -1
	c = 0
	a = list(map(int, input().split()))
	a.sort()
	for i in a:
		if i >= y:
			y = i * int(k) + int(b)
			c += 1
	print(c)


for _ in range(int(input())):
	(n, k, b) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	a.sort()
	count = 1
	y = k * a[0] + b
	for i in range(1, n):
		if y <= a[i]:
			y = k * a[i] + b
			count += 1
	print(count)


t = int(input())
for test in range(t):
	(n, k, b) = map(int, input().split())
	s = input()
	arr = [int(x) for x in s.split()]
	arr.sort()
	Ai = arr[0]
	listnew = []
	listnew.append(Ai)
	count = 1
	z = Ai * k + b
	for j in range(1, n):
		if arr[j] >= z:
			listnew.append(arr[j])
			Ai = arr[j]
			z = Ai * k + b
			count = count + 1
	print(count)


for _ in range(int(input())):
	(n, k, b) = [int(x) for x in input().split()]
	a = list(map(int, input().split()))
	a.sort()
	m = a[len(a) - 1]
	c = 0
	for i in range(len(a) - 2, -1, -1):
		if a[i] * k + b <= m:
			c += 1
			m = a[i]
	print(c + 1)


from bisect import bisect_right
T = int(input())
for query in range(T):
	(N, k, b) = [int(v) for v in input().split()]
	A = sorted([int(v) for v in input().split()])
	y = A.pop()
	count = 1
	while A:
		x = A.pop()
		if x * k + b <= y:
			count += 1
			y = x
	print(count)


for i in range(int(input())):
	(n, k, b) = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	l.sort()
	count = 1
	prev = 0
	for i in range(1, n):
		if l[i] >= k * l[prev] + b:
			count += 1
			prev = i
	print(count)


t = int(input())
while t:
	t -= 1
	(n, k, b) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	ans = 1
	val = a[0] * k + b
	for i in range(1, n):
		if a[i] >= val:
			val = a[i] * k + b
			ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, k, b) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	arr.sort()
	f = arr[0]
	ans = 0
	for i in range(1, n):
		if k * f + b <= arr[i]:
			ans += 1
			f = arr[i]
	print(ans + 1)


t = int(input())
for i in range(t):
	(n, k, b) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	seq = []
	seq.append(arr[0])
	count = 1
	ke = 0
	for j in range(1, n):
		if arr[j] >= k * arr[ke] + b:
			count += 1
			ke = j
	print(count)


t = int(input())
for I in range(t):
	(n, k, b) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	a.sort()
	ans = 1
	j = 0
	for i in range(1, len(a)):
		if a[i] >= k * a[j] + b:
			ans += 1
			j = i
	print(ans)


for _ in range(int(input())):
	(n, k, b) = [int(x) for x in input().split()]
	ar = [int(x) for x in input().split()]
	ar.sort()
	li = [i * k + b for i in ar]
	if n == 1:
		print(1)
	else:
		(i, j) = (0, 1)
		count = 1
		while j < n:
			if li[i] <= ar[j]:
				count += 1
				i = j
			j += 1
		print(count)


test = int(input())
for i in range(0, test):
	(N, k, b) = map(int, input().split(' '))
	A = list(map(int, input().split(' ')))
	A.sort()
	answer = 0
	curr = A[0]
	for j in range(1, N):
		if A[j] >= curr * k + b:
			answer += 1
			curr = A[j]
	print(answer + 1)


for _ in range(int(input())):
	(N, k, b) = (int(x) for x in input().split())
	l = [int(x) for x in input().split()]
	l.sort()
	T = [0 for i in range(N)]
	b1 = l[0]
	for i in range(1, N, 1):
		b2 = l[i]
		if b2 >= b1 * k + b:
			T[i] = T[i - 1] + 1
			b1 = l[i]
		else:
			T[i] = T[i - 1]
	print(T[N - 1] + 1)


T = int(input())
for _ in range(T):
	(N, k, b) = (int(i) for i in input().split())
	A = [int(i) for i in input().split()]
	A.sort()
	j = 0
	rep = 1
	for i in range(1, N):
		if A[i] >= k * A[j] + b:
			rep += 1
			j = i
	print(rep)


t = int(input())
for test in range(t):
	(n, k, b) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	i = 1
	ans = 0
	cur = a[0]
	while i < n:
		if cur * k + b <= a[i]:
			ans += 1
			cur = a[i]
		i += 1
	print(ans + 1)


from collections import defaultdict as dd
from itertools import permutations as pp
from math import *
from random import randint as rd
from bisect import bisect_left as bl
mod = 10 ** 9 + 7

def f(i, k, b):
	return k * i + b
for _ in range(int(input())):
	(n, k, b) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	a.sort()
	ans = 1
	j = 0
	for i in range(1, n):
		if a[i] >= f(a[j], k, b):
			ans += 1
			j = i
	print(ans)


def sol():
	(n, k, b) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	a = arr[0]
	ans = 0
	for i in range(1, n):
		if a * k + b <= arr[i]:
			ans += 1
			a = arr[i]
	return ans + 1
for _ in range(int(input())):
	print(sol())


for i in range(int(input())):
	ans = 0
	a = list(map(int, input().split()))
	List = list(map(int, input().split()))
	List.sort()
	j = 0
	num = List[0]
	for k in range(1, a[0]):
		if num * a[1] + a[2] <= List[k]:
			ans = ans + 1
			num = List[k]
	print(ans + 1)


for _ in range(int(input())):
	(n, k, b) = map(int, input().split())
	a = [int(x) for x in input().split()]
	a.sort()
	c = 0
	cur = a[0]
	i = 1
	while i < n:
		if cur * k + b <= a[i]:
			c += 1
			cur = a[i]
		i += 1
	print(c + 1)


for _ in range(int(input())):
	(n, k, b) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	i = 1
	count = 0
	curr = A[0]
	while i < n:
		if curr * k + b <= A[i]:
			count += 1
			curr = A[i]
		i += 1
	print(count + 1)


t = int(input())
for z in range(t):
	(n, k, b) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	a.sort()
	ans = 0
	a = a[::-1]
	tofind = a[0]
	for i in range(1, n):
		if a[i] * k + b <= tofind:
			ans += 1
			tofind = a[i]
	print(ans + 1)


import io
import sys

def test_data():
	return io.StringIO('1\n5 4 1\n100 2 4 17 8')

def get_input(source):
	with source as lines:
		t = int(next(lines))
		for _ in range(t):
			(n, k, b) = map(int, next(lines).split(' '))
			a = list(map(int, next(lines).split(' ')[:n]))
			yield (n, k, b, a)

def calc(n, k, b, a):
	a = sorted(a)
	ans = 1
	cur = k * a[0] + b
	for i in a[1:]:
		if cur <= i:
			ans += 1
			cur = k * i + b
	return ans
inp = test_data() if '-test' in sys.argv else sys.stdin
for args in get_input(inp):
	print(calc(*args))


for _ in range(int(input())):
	[n, k, b] = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	a.sort()
	ans = 1
	if k == 0 and b == 0 or (k == 1 and b == 0):
		print(n)
		continue
	if k == 0:
		for i in range(n):
			if a[i] >= b:
				print(n - i + 1 if i > 0 else n)
				break
		else:
			print(1)
		continue
	val = a[0] * k + b
	for i in range(1, n):
		if a[i] >= val:
			val = a[i] * k + b
			ans += 1
	print(ans)


for _ in range(int(input())):
	x = [int(x) for x in input().split()]
	y = [int(z) for z in input().split()]
	y.sort()
	j = 0
	count = 1
	for i in range(1, len(y)):
		if y[i] >= y[j] * x[1] + x[2]:
			count += 1
			j = i
	print(count)


t = int(input())
for i in range(t):
	(n, k, b) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	a.sort(reverse=True)
	l = len(a)
	c = 0
	m = 0
	for j in range(1, l):
		y = k * a[j] + b
		if y <= a[m]:
			c += 1
			m = j
	print(c + 1)


n = int(input())
for i in range(n):
	(n1, k, b) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = []
	l.sort()
	for i in range(len(l)):
		l1.append(l[i] * k + b)
	if n1 == 1:
		print('1')
	else:
		j = 1
		i1 = 0
		c = 1
		while j < n1:
			if l1[i1] <= l[j]:
				c += 1
				i1 = j
			j += 1
		print(c)


for _ in range(int(input())):
	count = 0
	(n, k, b) = map(int, input().split())
	list1 = list(map(int, input().split()))
	list2 = sorted(list1)
	list3 = []
	for i in list2:
		list3.append(i * k + b)
	j = len(list3) - 1
	for i in range(len(list2) - 2, -1, -1):
		if list3[i] <= list2[j]:
			j = i
			count += 1
	print(count + 1)


t = int(input())

def ans(x, l, n):
	i = 0
	j = 1
	count = 1
	while j < n:
		if x[i] <= l[j]:
			count = count + 1
			i = j
		j = j + 1
	return count
for i in range(t):
	(n, k, b) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	count = 1
	x = [0] * n
	for i in range(n):
		x[i] = l[i] * k + b
	if n == 1:
		print('1')
	else:
		print(ans(x, l, n))


for _ in range(int(input())):
	(n, k, b) = map(int, input().split())
	ar = list(map(int, input().split()))
	ar.sort()
	new = [i * k + b for i in ar]
	if n == 1:
		print(1)
	else:
		(i, j) = (0, 1)
		count = 1
		while j < n:
			if new[i] <= ar[j]:
				count += 1
				i = j
			j += 1
		print(count)


import collections
T = int(input())
for _ in range(T):
	(N, K, B) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	A.sort()
	A = collections.deque(A)
	elementsLeft = N
	elementsChosen = 0
	currentElement = A.popleft()
	elementsLeft -= 1
	elementsChosen += 1
	target = K * currentElement + B
	while elementsLeft > 0:
		newElement = A.popleft()
		elementsLeft -= 1
		if newElement >= target:
			currentElement = newElement
			elementsChosen += 1
			target = K * currentElement + B
		else:
			pass
	print(elementsChosen)


t = int(input())
for _ in range(t):
	(n, k, b) = map(int, input().split())
	A = sorted((int(x) for x in input().split()))
	last = A[0]
	cnt = 1
	for i in range(1, n):
		if A[i] >= k * last + b:
			cnt += 1
			last = A[i]
	print(cnt)


def isReachable(y, x, k, b):
	return y >= k * x + b
T = int(input())
for testCase in range(T):
	(N, k, b) = list(map(int, input().split()))
	A = sorted(list(map(int, input().split())))
	maxi = 1
	loc = 0
	for i in range(1, N):
		if isReachable(A[i], A[loc], k, b):
			maxi += 1
			loc = i
	print(maxi)


def solve():
	(n, k, b) = (int(x) for x in input().split())
	arr = [int(x) for x in input().split()]
	arr = sorted(arr)
	good = True
	length = 1
	last_val = arr[0]
	for idx in range(1, n):
		if arr[idx] >= k * last_val + b:
			length += 1
			last_val = arr[idx]
	print(length)
t = int(input())
for _ in range(t):
	solve()


t = int(input())
for _ in range(t):
	(n, k, b) = map(int, input().split())
	s = list(map(int, input().split()))
	p = []
	s.sort()
	for i in range(n):
		p.append([s[i], s[i] * k + b])
	i = 1
	count = 1
	maxx = p[0][1]
	while i < n:
		if p[i][0] >= maxx:
			count += 1
			maxx = p[i][1]
		i += 1
	print(count)