Manhattan Mornings

Choose a monotone shortest path from house to workplace on the Manhattan grid that passes through as many errand points as possible.

Medium7Dynamic programmingSortingArrayNo attempts yetTime limit2sMemory limit512 MB

Problem

As a New Yorker you are always busy. Your workday is long, and on top of that you keep a long list of errands to run on any given day. You hate getting up early, so you always work through the list after the office, and that is eating into your free time.

One day you notice that some of the places you have to visit lie on your walk to the office, so you can stop there before work. The next day you notice that a slightly different route lets you run most of your errands without making the walk any longer. An errand takes a negligible amount of time, so you do not have to get up any earlier. This effect of the grid-like New York streets gets you thinking. Given the locations of all your errands on the New York grid, how many of them can you visit on the way to work without getting up any earlier?

The New York grid is modelled with streets parallel to the xx-axis and avenues parallel to the yy-axis. There is a street y=ay = a for every integer aa, and there is an avenue x=bx = b for every integer bb. An errand always takes place at an intersection of a street and an avenue. You walk to work, so you can use every road in both directions.

Input

  • The first line contains an integer nn, the number of errands you have to run that day (0n1050 \le n \le 10^5).
  • The second line contains four integers xhx_h, yhy_h, xwx_w, ywy_w, the coordinates of your house and of your workplace (0xh,yh,xw,yw1090 \le x_h, y_h, x_w, y_w \le 10^9).
  • Each of the next nn lines contains two integers xix_i and yiy_i, the coordinates of your ii-th errand (0xi,yi1090 \le x_i, y_i \le 10^9).

Several errands can take place at one intersection, and each of them is counted separately.

Output

Print one line with the largest number of errands you can run before work on a route that is no longer than the shortest walk from your house to your workplace.