#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cassert>
#include<climits>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)
#define MAX 40000
#define EPS (1e-6)
#define COUNTER_CLOCKWISE 1
#define CLOCKWISE -1 
#define ONLINE_BACK 2
#define ONLINE_FRONT -2
#define ON_SEGMENT 0
#define equals(a,b) (fabs((a)-(b)) < EPS)

using namespace std;

// Library - template - begin

class Point
{
  public:
  double x,y;

  Point(double x = -IINF,double y = -IINF): x(x),y(y){}

  Point operator + (Point p){return Point(x+p.x,y+p.y);}
  Point operator - (Point p){return Point(x-p.x,y-p.y);}
  Point operator * (double a){return Point(a*x,a*y);}
  Point operator / (double a){return Point(x/a,y/a);}
  Point operator * (Point a){ return Point(x * a.x - y * a.y, x * a.y + y * a.x); }

  bool operator < (const Point& p) const
  {
    return !equals(y,p.y)?y<p.y:x<p.x;
  }

  bool operator == (const Point& p)const
  {
    return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
  }

};

struct Segment
{
  Point p1,p2;
  Segment(Point p1 = Point(),Point p2 = Point()):p1(p1),p2(p2){}
  bool operator == (const Segment& p)const
  {
    return p.p1 == p1 && p.p2 == p2;
  }
};

typedef Point Vector;
typedef Segment Line;
typedef vector<Point> Polygon;

ostream& operator << (ostream& os,const Point& a)
{
  os << "(" << a.x << "," << a.y << ")";
}

ostream& operator << (ostream& os,const Segment& a)
{
  os << "( " << a.p1 << " , " << a.p2 << " )";
}

double dot(Point a,Point b){ return a.x*b.x + a.y*b.y; }

double cross(Point a,Point b){ return a.x*b.y - a.y*b.x; }

double norm(Point a){ return a.x*a.x+a.y*a.y; }

double abs(Point a){ return sqrt(norm(a)); }

//rad テ」ツ?ッティツァツ津・ツコツヲテ」ツつ津」ツδゥテ」ツつクテ」ツつ「テ」ツδウテ」ツ?ァテヲツ個?」ツ?淌」ツ?崚」ツつ凝」ツ?禿」ツ?ィ
Point rotate(Point a,double rad){ return Point(cos(rad)*a.x - sin(rad)*a.y,sin(rad)*a.x + cos(rad)*a.y); }

// テ・ツコツヲテ」ツつ津」ツδゥテ」ツつクテ」ツつ「テ」ツδウテ」ツ?ォテ・ツ、ツ嘉ヲツ渉?
double toRad(double agl){ return agl*M_PI/180.0; }

// Library - template - end

// Library - ccw - begin

int ccw(Point p0,Point p1,Point p2){
  Point a = p1-p0;
  Point b = p2-p0;
  if(cross(a,b) > EPS)return COUNTER_CLOCKWISE;
  if(cross(a,b) < -EPS)return CLOCKWISE;
  if(dot(a,b) < -EPS)return ONLINE_BACK;
  if(norm(a) < norm(b))return ONLINE_FRONT;
  return ON_SEGMENT;
}

// Library - ccw - end

// Library - inPolygon - begin

//cross product of pq and pr
double cross3p(Point p,Point q,Point r)
{
  return (r.x-q.x) * (p.y -q.y) - (r.y - q.y) * (p.x - q.x);
}
  
//returns true if point r is on the same line as the line pq
bool collinear(Point p,Point q,Point r)
{
  return fabs(cross3p(p,q,r)) < EPS;
}
  
//returns true if point t is on the left side of line pq
bool ccwtest(Point p,Point q,Point r)
{
  return cross3p(p,q,r) > 0;//can be modified to accept collinear points
}
 
bool onSegment(Point p,Point q,Point r)
{
  return collinear(p,q,r) && equals(sqrt(pow(p.x-r.x,2)+pow(p.y-r.y,2)) + sqrt(pow(r.x-q.x,2) + pow(r.y-q.y,2) ),sqrt(pow(p.x-q.x,2)+pow(p.y-q.y,2)) ) ;
}
  

bool isConvex(vector<Point> p)
{
  int sz = (int)p.size();
  
  if(sz < 3)return false;//boundary case, we treat a point or a line as not convex
  
  bool isLeft = ccwtest(p[0],p[1],p[2]);
  
  for(int i=1; i<(int)p.size();i++)
    if(ccwtest(p[i],p[(i+1)%sz],p[(i+2)%sz]) != isLeft)
      return false;
  
  return true;
}


double angle(Point a,Point b,Point c)
{
  double ux = b.x - a.x, uy = b.y - a.y;
  double vx = c.x - a.x, vy = c.y - a.y;
  return acos((ux*vx + uy*vy)/sqrt((ux*ux + uy*uy) * (vx*vx + vy*vy)));
}  
  
//テ・ツ、ツ堙ィツァツ津・ツスツ「polyテ・ツ??ッツシツ暗ァツキツ堙・ツ按?、ツクツ甘」ツつづ・ツ青ォテ」ツつ?ッツシツ嘉」ツ?ォテァツつケpテ」ツ?古・ツュツ佚・ツ慊ィテ」ツ?凖」ツつ凝」ツ?凝」ツ?ゥテ」ツ??」ツ?ッテ・ツ按、テ・ツョツ堙」ツ?凖」ツつ? 
bool inPolygon(Polygon poly,Point p)
{
  if((int)poly.size() == 0)return false;

  rep(i,poly.size())
  if(onSegment(poly[i],poly[(i+1)%poly.size()],p))return true;
  double sum = 0;
  for(int i=0; i < (int)poly.size() ;i++)
    {
      if(cross3p(p,poly[i],poly[(i+1)%poly.size()]) < 0)
	sum -= angle(p,poly[i],poly[(i+1)%poly.size()]);
      else
	sum += angle(p,poly[i],poly[(i+1)%poly.size()]);
    }
  return (fabs(sum - 2*M_PI) < EPS || fabs(sum + 2*M_PI) < EPS);

}  

// Library - inPolygon - end

// Library - area - begin

double getArea(vector<Point> vec)
{
  double sum = 0;
  for(int i=0;i<vec.size();i++)
    sum += cross(vec[i],vec[(i+1)%vec.size()]);
  return fabs(sum)/2.0;
}

// Library - area - end

int n,m,w,h,s;
double S,l[MAX],r[MAX];
Point ps[MAX];
Polygon poly[MAX];
int almond[MAX],talmond[MAX];
double area[MAX],total[MAX];

bool check(int M,int index){
  Polygon npoly;
  int len = poly[M].size();
  npoly.push_back(poly[M][len-2]), npoly.push_back(poly[M][len-1]);
  if(!(npoly[1] == Point(0,0)))npoly.push_back(Point(0,0));
  if(!(npoly[0] == Point(w,0)))npoly.push_back(Point(w,0));
  return inPolygon(npoly,ps[index]);
}


int main(){

  while(cin >> n >> m >> w >> h >> s,n|m|w|h|s){
    S = s;
    Point p1 = Point(0,0);
    Point p2 = Point((double)w,0);
    double debug = 0;
    rep(i,m){
      almond[i] = 0;
      poly[i].clear();
      cin >> l[i] >> r[i];
      if(!(p1 == Point(0,l[i])))
      poly[i].push_back(p1);
      poly[i].push_back(p2);
      if(!(Point(w,r[i]) == p2))
	poly[i].push_back(Point(w,r[i]));
      poly[i].push_back(Point(0,l[i]));
      p1 = Point(0,l[i]), p2 = Point((double)w,r[i]);
      area[i] = getArea(poly[i]);
      debug += area[i];
      almond[i] = 0;
    }

    rep(i,n) cin >> ps[i].x >> ps[i].y;

    if(s == 0){
      cout << 0 << endl;
      continue;
    }

    rep(i,n){
      int L = 0, R = m,M;
      while(L < R){
	M = (L+R)/2;
	if(inPolygon(poly[M],ps[i])) break;
	else if(check(M,i)) R = M;
	else L = M+1;
      }
      if(inPolygon(poly[M],ps[i]))almond[M]++;
      else if(inPolygon(poly[L],ps[i]))almond[L]++;
      else if(R<m&&inPolygon(poly[R],ps[i]))almond[R]++;
      else assert(false);
    }

    total[0] = area[m-1];
    talmond[0] = almond[m-1];
    REP(i,1,m){
      total[i] = total[i-1] + area[m-1-i];
      talmond[i] = talmond[i-1] + almond[m-1-i];
    }

    int ans = IINF;
    double remain = 0;
    int counter = 0;
    int pos = lower_bound(total,total+m,S) - total;
    ans = min(ans,talmond[pos]);

    rep(i,m){
      double cost = ( (i == m-1) ? 0 : total[m-1-i-1] );
      int cost2 =   ( (i == m-1) ? 0 : talmond[m-1-i-1]);
      remain = total[m-1] - cost;
      counter = talmond[m-1] - cost2;
      if(equals(remain,S) || remain > S){
	ans = min(ans,counter);
	continue;
      }
      pos = lower_bound(total,total+m,(double)(S-remain)) - total;
      if(m-1-pos <= i)continue;
      double fofpwaejfoaw = total[pos] + remain;
      if(equals(fofpwaejfoaw,S) || fofpwaejfoaw > S){
	int add = talmond[pos];
	ans = min(ans,add+counter);
      }
    }
    cout << ans << endl;
  }
  return 0;
}
### Prompt

Generate a CPP solution to the following problem:

Turtle Shi-ta and turtle Be-ko decided to divide a chocolate. The shape of the chocolate is rectangle. The corners of the chocolate are put on (0,0), (w,0), (w,h) and (0,h). The chocolate has lines for cutting. They cut the chocolate only along some of these lines.

The lines are expressed as follows. There are  m  points on the line connected between (0,0) and (0,h), and between (w,0) and (w,h). Each i-th point, ordered by y value (i = 0 then y =0), is connected as cutting line. These lines do not share any point where 0 < x < w . They can share points where x = 0 or x = w . However, (0, li ) = (0,lj ) and (w,ri ) = (w,rj ) implies  i  =  j  . The following figure shows the example of the chocolate.

<image>

There are  n  special almonds, so delicious but high in calories on the chocolate. Almonds are circle but their radius is too small. You can ignore radius of almonds. The position of almond is expressed as (x,y) coordinate.

Two turtles are so selfish. Both of them have requirement for cutting.

Shi-ta's requirement is that the piece for her is continuous. It is possible for her that she cannot get any chocolate. Assume that the minimum index of the piece is  i  and the maximum is  k . She must have all pieces between  i  and  k . For example, chocolate piece 1,2,3 is continuous but 1,3 or 0,2,4 is not continuous.

Be-ko requires that the area of her chocolate is at least  S . She is worry about her weight. So she wants the number of almond on her chocolate is as few as possible.

They doesn't want to make remainder of the chocolate because the chocolate is expensive.

Your task is to compute the minumum number of Beko's almonds if both of their requirment are satisfied.



Input

Input consists of multiple test cases.
Each dataset is given in the following format.


n m w h S
l0 r0
...
lm-1 rm-1
x0 y0
...
xn-1 yn-1


The last line contains five 0s. n is the number of almonds. m is the number of lines. w is the width of the chocolate. h is the height of the chocolate. S is the area that Be-ko wants to eat. Input is integer except xi yi.

Input satisfies following constraints.
1 ≤ n ≤ 30000
1 ≤ m ≤ 30000
1 ≤ w ≤ 200
1 ≤ h ≤ 1000000
0 ≤ S ≤ w*h


If i < j  then  li ≤ lj and  ri ≤ rj and then  i -th lines and  j -th lines share at most 1 point. It is assured that lm-1 and rm-1 are h. xi yi is floating point number with ten digits. It is assured that they are inside of the chocolate. It is assured that the distance between points and any lines is at least 0.00001.

Output

You should output the minumum number of almonds for Be-ko.

Example

Input

2 3 10 10 50
3 3
6 6
10 10
4.0000000000 4.0000000000
7.0000000000 7.0000000000
2 3 10 10 70
3 3
6 6
10 10
4.0000000000 4.0000000000
7.0000000000 7.0000000000
2 3 10 10 30
3 3
6 6
10 10
4.0000000000 4.0000000000
7.0000000000 7.0000000000
2 3 10 10 40
3 3
6 6
10 10
4.0000000000 4.0000000000
7.0000000000 7.0000000000
2 3 10 10 100
3 3
6 6
10 10
4.0000000000 4.0000000000
7.0000000000 7.0000000000
0 0 0 0 0


Output

1
1
0
1
2

### Response

```cpp
#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cassert>
#include<climits>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)
#define MAX 40000
#define EPS (1e-6)
#define COUNTER_CLOCKWISE 1
#define CLOCKWISE -1 
#define ONLINE_BACK 2
#define ONLINE_FRONT -2
#define ON_SEGMENT 0
#define equals(a,b) (fabs((a)-(b)) < EPS)

using namespace std;

// Library - template - begin

class Point
{
  public:
  double x,y;

  Point(double x = -IINF,double y = -IINF): x(x),y(y){}

  Point operator + (Point p){return Point(x+p.x,y+p.y);}
  Point operator - (Point p){return Point(x-p.x,y-p.y);}
  Point operator * (double a){return Point(a*x,a*y);}
  Point operator / (double a){return Point(x/a,y/a);}
  Point operator * (Point a){ return Point(x * a.x - y * a.y, x * a.y + y * a.x); }

  bool operator < (const Point& p) const
  {
    return !equals(y,p.y)?y<p.y:x<p.x;
  }

  bool operator == (const Point& p)const
  {
    return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
  }

};

struct Segment
{
  Point p1,p2;
  Segment(Point p1 = Point(),Point p2 = Point()):p1(p1),p2(p2){}
  bool operator == (const Segment& p)const
  {
    return p.p1 == p1 && p.p2 == p2;
  }
};

typedef Point Vector;
typedef Segment Line;
typedef vector<Point> Polygon;

ostream& operator << (ostream& os,const Point& a)
{
  os << "(" << a.x << "," << a.y << ")";
}

ostream& operator << (ostream& os,const Segment& a)
{
  os << "( " << a.p1 << " , " << a.p2 << " )";
}

double dot(Point a,Point b){ return a.x*b.x + a.y*b.y; }

double cross(Point a,Point b){ return a.x*b.y - a.y*b.x; }

double norm(Point a){ return a.x*a.x+a.y*a.y; }

double abs(Point a){ return sqrt(norm(a)); }

//rad テ」ツ?ッティツァツ津・ツコツヲテ」ツつ津」ツδゥテ」ツつクテ」ツつ「テ」ツδウテ」ツ?ァテヲツ個?」ツ?淌」ツ?崚」ツつ凝」ツ?禿」ツ?ィ
Point rotate(Point a,double rad){ return Point(cos(rad)*a.x - sin(rad)*a.y,sin(rad)*a.x + cos(rad)*a.y); }

// テ・ツコツヲテ」ツつ津」ツδゥテ」ツつクテ」ツつ「テ」ツδウテ」ツ?ォテ・ツ、ツ嘉ヲツ渉?
double toRad(double agl){ return agl*M_PI/180.0; }

// Library - template - end

// Library - ccw - begin

int ccw(Point p0,Point p1,Point p2){
  Point a = p1-p0;
  Point b = p2-p0;
  if(cross(a,b) > EPS)return COUNTER_CLOCKWISE;
  if(cross(a,b) < -EPS)return CLOCKWISE;
  if(dot(a,b) < -EPS)return ONLINE_BACK;
  if(norm(a) < norm(b))return ONLINE_FRONT;
  return ON_SEGMENT;
}

// Library - ccw - end

// Library - inPolygon - begin

//cross product of pq and pr
double cross3p(Point p,Point q,Point r)
{
  return (r.x-q.x) * (p.y -q.y) - (r.y - q.y) * (p.x - q.x);
}
  
//returns true if point r is on the same line as the line pq
bool collinear(Point p,Point q,Point r)
{
  return fabs(cross3p(p,q,r)) < EPS;
}
  
//returns true if point t is on the left side of line pq
bool ccwtest(Point p,Point q,Point r)
{
  return cross3p(p,q,r) > 0;//can be modified to accept collinear points
}
 
bool onSegment(Point p,Point q,Point r)
{
  return collinear(p,q,r) && equals(sqrt(pow(p.x-r.x,2)+pow(p.y-r.y,2)) + sqrt(pow(r.x-q.x,2) + pow(r.y-q.y,2) ),sqrt(pow(p.x-q.x,2)+pow(p.y-q.y,2)) ) ;
}
  

bool isConvex(vector<Point> p)
{
  int sz = (int)p.size();
  
  if(sz < 3)return false;//boundary case, we treat a point or a line as not convex
  
  bool isLeft = ccwtest(p[0],p[1],p[2]);
  
  for(int i=1; i<(int)p.size();i++)
    if(ccwtest(p[i],p[(i+1)%sz],p[(i+2)%sz]) != isLeft)
      return false;
  
  return true;
}


double angle(Point a,Point b,Point c)
{
  double ux = b.x - a.x, uy = b.y - a.y;
  double vx = c.x - a.x, vy = c.y - a.y;
  return acos((ux*vx + uy*vy)/sqrt((ux*ux + uy*uy) * (vx*vx + vy*vy)));
}  
  
//テ・ツ、ツ堙ィツァツ津・ツスツ「polyテ・ツ??ッツシツ暗ァツキツ堙・ツ按?、ツクツ甘」ツつづ・ツ青ォテ」ツつ?ッツシツ嘉」ツ?ォテァツつケpテ」ツ?古・ツュツ佚・ツ慊ィテ」ツ?凖」ツつ凝」ツ?凝」ツ?ゥテ」ツ??」ツ?ッテ・ツ按、テ・ツョツ堙」ツ?凖」ツつ? 
bool inPolygon(Polygon poly,Point p)
{
  if((int)poly.size() == 0)return false;

  rep(i,poly.size())
  if(onSegment(poly[i],poly[(i+1)%poly.size()],p))return true;
  double sum = 0;
  for(int i=0; i < (int)poly.size() ;i++)
    {
      if(cross3p(p,poly[i],poly[(i+1)%poly.size()]) < 0)
	sum -= angle(p,poly[i],poly[(i+1)%poly.size()]);
      else
	sum += angle(p,poly[i],poly[(i+1)%poly.size()]);
    }
  return (fabs(sum - 2*M_PI) < EPS || fabs(sum + 2*M_PI) < EPS);

}  

// Library - inPolygon - end

// Library - area - begin

double getArea(vector<Point> vec)
{
  double sum = 0;
  for(int i=0;i<vec.size();i++)
    sum += cross(vec[i],vec[(i+1)%vec.size()]);
  return fabs(sum)/2.0;
}

// Library - area - end

int n,m,w,h,s;
double S,l[MAX],r[MAX];
Point ps[MAX];
Polygon poly[MAX];
int almond[MAX],talmond[MAX];
double area[MAX],total[MAX];

bool check(int M,int index){
  Polygon npoly;
  int len = poly[M].size();
  npoly.push_back(poly[M][len-2]), npoly.push_back(poly[M][len-1]);
  if(!(npoly[1] == Point(0,0)))npoly.push_back(Point(0,0));
  if(!(npoly[0] == Point(w,0)))npoly.push_back(Point(w,0));
  return inPolygon(npoly,ps[index]);
}


int main(){

  while(cin >> n >> m >> w >> h >> s,n|m|w|h|s){
    S = s;
    Point p1 = Point(0,0);
    Point p2 = Point((double)w,0);
    double debug = 0;
    rep(i,m){
      almond[i] = 0;
      poly[i].clear();
      cin >> l[i] >> r[i];
      if(!(p1 == Point(0,l[i])))
      poly[i].push_back(p1);
      poly[i].push_back(p2);
      if(!(Point(w,r[i]) == p2))
	poly[i].push_back(Point(w,r[i]));
      poly[i].push_back(Point(0,l[i]));
      p1 = Point(0,l[i]), p2 = Point((double)w,r[i]);
      area[i] = getArea(poly[i]);
      debug += area[i];
      almond[i] = 0;
    }

    rep(i,n) cin >> ps[i].x >> ps[i].y;

    if(s == 0){
      cout << 0 << endl;
      continue;
    }

    rep(i,n){
      int L = 0, R = m,M;
      while(L < R){
	M = (L+R)/2;
	if(inPolygon(poly[M],ps[i])) break;
	else if(check(M,i)) R = M;
	else L = M+1;
      }
      if(inPolygon(poly[M],ps[i]))almond[M]++;
      else if(inPolygon(poly[L],ps[i]))almond[L]++;
      else if(R<m&&inPolygon(poly[R],ps[i]))almond[R]++;
      else assert(false);
    }

    total[0] = area[m-1];
    talmond[0] = almond[m-1];
    REP(i,1,m){
      total[i] = total[i-1] + area[m-1-i];
      talmond[i] = talmond[i-1] + almond[m-1-i];
    }

    int ans = IINF;
    double remain = 0;
    int counter = 0;
    int pos = lower_bound(total,total+m,S) - total;
    ans = min(ans,talmond[pos]);

    rep(i,m){
      double cost = ( (i == m-1) ? 0 : total[m-1-i-1] );
      int cost2 =   ( (i == m-1) ? 0 : talmond[m-1-i-1]);
      remain = total[m-1] - cost;
      counter = talmond[m-1] - cost2;
      if(equals(remain,S) || remain > S){
	ans = min(ans,counter);
	continue;
      }
      pos = lower_bound(total,total+m,(double)(S-remain)) - total;
      if(m-1-pos <= i)continue;
      double fofpwaejfoaw = total[pos] + remain;
      if(equals(fofpwaejfoaw,S) || fofpwaejfoaw > S){
	int add = talmond[pos];
	ans = min(ans,add+counter);
      }
    }
    cout << ans << endl;
  }
  return 0;
}
```