====== 가톨릭대는 고양이를 사랑해 ======

===== 풀이 =====
  * [[ps:tutorial:격자 경로#방문할_때_1점을_얻는_점이_k개_있을_때|격자 경로에서 가장 많은 점수를 얻는 이동 경로]]를 찾는 문제이다.
  * 링크에서 설명한대로 [[ps:tutorial:lis]]를 이용해서 O(klogk)에 풀 수 있다.
  * 가톨릭대 밖에 고양이가 존재할수 있다는 조건은 왜 굳이 넣어서 그냥 쓸데없이 귀찮게 만들었는지는 모르겠다...


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 23035. 가톨릭대는 고양이를 사랑해".

- Problem link: https://www.acmicpc.net/problem/23035
- Solution link: http://www.teferi.net/ps/problems/boj/23035

Tags: [LIS]
"""

import sys
from teflib import seqtask


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    T = int(sys.stdin.readline())
    poses = []
    for _ in range(T):
        r_i, c_i = [int(x) - 1 for x in sys.stdin.readline().split()]
        if r_i < N and c_i < M:
            poses.append((r_i, c_i))

    seq = [c for r, c in sorted(poses)]
    answer = seqtask.longest_inc_subseq_length(seq, strict=False)

    print(answer)


if __name__ == '__main__':
    main()
</dkpr>

  * Dependency: [[:ps:teflib:seqtask#longest_inc_subseq_length|teflib.seqtask.longest_inc_subseq_length]]

{{tag>BOJ ps:problems:boj:플래티넘_4}}