This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
from sys import stdin
input = stdin.readline
L, N = map(int, input().split())
arr = [map(int, input().split()) for i in xrange(N)]
arr.sort()
brr = [float(L) / j + i for i, j in arr][::-1]
# count LIS
def lis(n, arr, output = False):
    d = [0] * (n + 1)
    p = [0] * (n + 1)
    L = 0
    for i in xrange(n):
        low = 1
        high = L
        while low <= high:
            mid = (low + high) / 2
            if arr[d[mid]] < arr[i]: low = mid + 1
            else: high = mid - 1
        p[i] = d[low - 1]
        d[low] = i
        L = max(L, low)
    print L
    if output:
        ans = []
        k = d[L]
        for i in xrange(L):
            ans.append(arr[k])
            k = p[k]
        print " ".join(map(str, ans[::-1]))
lis(N, brr)
| # | Verdict | Execution time | Memory | Grader output | 
|---|
| Fetching results... | 
| # | Verdict | Execution time | Memory | Grader output | 
|---|
| Fetching results... | 
| # | Verdict | Execution time | Memory | Grader output | 
|---|
| Fetching results... | 
| # | Verdict | Execution time | Memory | Grader output | 
|---|
| Fetching results... | 
| # | Verdict | Execution time | Memory | Grader output | 
|---|
| Fetching results... |