The Legend of Zelda

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

 

Fish 真的非常喜欢打游戏,最近又沉迷于塞尔达传说,现在 Fish 刚刚打通了雷咒盖侬解放了神兽瓦·纳波利斯,准备前往死亡火山去挑战火咒盖侬。

 

现在 Fish 刚刚回到了格鲁德小镇上,我们知道死亡火山在地图的右上角,但是格鲁德小镇在地图的左下角,之间有非常远的距离,地图上会有不少的驿站用来休息,但是 Fish 不想为了路过驿站而走远路,现在 Fish 想安排一个旅行的路线,使得经过的驿站尽可能的多,请你编写一个程序帮助他!

 

抽象一下题意,在一个二维坐标轴上,现在给出起点终点和 N 个点 Pi 的坐标,选择尽可能多的点组成一个序列,使得序列中点的 x 和 y 坐标都是递增的。

Input

多组输入(不超过10组)

 对于每组数据:

  • 第一行包括四个数 x1,y1,x2,y2,分别代表起点的横纵坐标,终点的横纵坐标(x1 < x2, y1 < y2)
  • 第二行输入一个整数 N,代表有 N 个点
  • 接下来 N 行,每行输入一个点的坐标 xi,yi 

 

0 <= N <= 1000

保证所有点的坐标大小在 32 位整数之内

Output

每组数据输出一行整数,为找出的最长序列长度(包含起点和终点)

Sample Input

1 1 9 9
5
0 8
3 2
3 3
4 3
7 1

Sample Output

4

Hint

第一组样例找出的最长序列只有 {(1, 1), (3, 2), (4, 3), (9, 9)} 长度为 4

Source

【2017级《程序设计基础(B)II》期末上机考试】Fish_li