#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 30005

class Point{
public:
	double x,y;

	Point(double x = 0,double y = 0):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); }

	double abs(){ return sqrt(norm()); }
	double norm(){ return x*x + y*y; }

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

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

typedef Point Vector;
typedef vector<Point> Polygon;

struct Info{
	int value;
	Polygon polygon;
	double min_y,max_y,S;
};

int num_almond,num_section;
int ruiseki_value[NUM];
double W,H,total_S,need_S;
double ruiseki_S[NUM];
Info info[NUM];
Point pre_L,pre_R,L,R;

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

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

//ベクトルaとbの外積を求める関数
double cross(Vector a,Vector b){
	return a.x*b.y-a.y*b.x;
}

//ベクトルaとbの内積を求める関数
double dot(Vector a,Vector b){
	return a.x*b.x + a.y*b.y;
}

Point calc_minus(Point a,Point b){
	Point ret;

	ret.x = a.x-b.x;
	ret.y = a.y-b.y;

	return ret;
}

/*
 * IN 2
 * ON 1
 * OUT 0
 *
 */
int contains(Polygon g,Point p){
	int n = g.size();
	bool x = false;
	for(int i = 0; i < n; i++){
		Point a = g[i]-p,b = g[(i+1)%n]-p;
		if(abs(cross(a,b)) < EPS && dot(a,b) < EPS)return 1;
		if(a.y > b.y)swap(a,b);
		if(a.y < EPS && EPS < b.y && cross(a,b) > EPS) x = !x;
	}
	return (x ? 2:0);
}

void func(){

	for(int i = 0; i < num_section; i++){
		info[i].value = 0; //断片内のアーモンドの個数
		info[i].polygon.clear();
	}

	pre_L.x = 0;
	pre_R.x = W;

	pre_L.y = 0;
	pre_R.y = 0;

	L.x = 0;
	R.x = W;

	for(int i = 0; i < num_section; i++){

		scanf("%lf %lf",&L.y,&R.y);

		//左下から反時計回りに点を記録
		info[i].polygon.push_back(pre_L);
		info[i].polygon.push_back(pre_R);
		info[i].polygon.push_back(R);
		info[i].polygon.push_back(L);

		info[i].min_y = min(pre_L.y,pre_R.y);
		info[i].max_y = max(L.y,R.y);

		info[i].S = (((L.y-pre_L.y)+(R.y-pre_R.y))*W)/2.0; //台形の面積

		pre_L = L;
		pre_R = R;
	}

	//アーモンドの処理
	Point tmp;
	int left,right,m;
	int min_index,max_index;

	for(int loop = 0; loop < num_almond; loop++){

		scanf("%lf %lf",&tmp.x,&tmp.y);

		//アーモンドが所属し得る最小のインデックスを求める
		left = 0,right = num_section-1,m = (left+right)/2;
		min_index = num_section-1;

		while(left <= right){
			if(info[m].max_y > tmp.y){

				min_index = m;
				right = m-1;

			}else{

				left = m+1;

			}
			m = (left+right)/2;
		}

		//アーモンドが所属し得る最大のインデックスを求める
		left = 0,right = num_section-1,m = (left+right)/2;
		max_index = 0;

		while(left <= right){

			if(info[m].min_y < tmp.y){

				max_index = m;
				left = m+1;

			}else{

				right = m-1;
			}
			m = (left+right)/2;
		}

		if(min_index > max_index)continue;

		for(int i = min_index; i <= max_index; i++){

			if(contains(info[i].polygon,tmp) == 2){ //問題仕様上、ONは無いはず
				info[i].value++;
				break;
			}
		}
	}

	//累積和テーブルを作成する
	ruiseki_S[0] = info[0].S;
	ruiseki_value[0] = info[0].value;

	for(int i = 1; i < num_section; i++){
		ruiseki_S[i] = info[i].S;
		ruiseki_S[i] += ruiseki_S[i-1];
		ruiseki_value[i] = info[i].value;
		ruiseki_value[i] += ruiseki_value[i-1];
	}

	total_S = H*W;
	int ans = num_almond;

	double tmp_S;
	int tmp_almond;

	for(int i = 0; i < num_section; i++){
		/*★シータの面積は大きいほど良い★*/

		//2分探索で、残チョコの面積がS以上となる、最大の上端を求める
		left = 0,right = num_section-1,m = (left+right)/2;

		while(left <= right){
			//シータの面積を求める
			if(i != 0){

				tmp_S = ruiseki_S[m]-ruiseki_S[i-1];

			}else{

				tmp_S = ruiseki_S[m];
			}

			if(total_S-tmp_S >= need_S){ //残りがneed_S以上

				if(i != 0){

					tmp_almond = ruiseki_value[m]-ruiseki_value[i-1];

				}else{

					tmp_almond = ruiseki_value[m];
				}

				ans = min(ans,num_almond-tmp_almond);

				left = m+1;

			}else{
				right = m-1;
			}
			m = (left+right)/2;
		}
	}
	printf("%d\n",ans);
}

int main(){

	while(true){
		scanf("%d %d %lf %lf %lf",&num_almond,&num_section,&W,&H,&need_S);
		if(num_almond == 0 && num_section == 0)break;

		func();
	}
	return 0;
}


### Prompt

Please formulate 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<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 30005

class Point{
public:
	double x,y;

	Point(double x = 0,double y = 0):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); }

	double abs(){ return sqrt(norm()); }
	double norm(){ return x*x + y*y; }

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

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

typedef Point Vector;
typedef vector<Point> Polygon;

struct Info{
	int value;
	Polygon polygon;
	double min_y,max_y,S;
};

int num_almond,num_section;
int ruiseki_value[NUM];
double W,H,total_S,need_S;
double ruiseki_S[NUM];
Info info[NUM];
Point pre_L,pre_R,L,R;

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

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

//ベクトルaとbの外積を求める関数
double cross(Vector a,Vector b){
	return a.x*b.y-a.y*b.x;
}

//ベクトルaとbの内積を求める関数
double dot(Vector a,Vector b){
	return a.x*b.x + a.y*b.y;
}

Point calc_minus(Point a,Point b){
	Point ret;

	ret.x = a.x-b.x;
	ret.y = a.y-b.y;

	return ret;
}

/*
 * IN 2
 * ON 1
 * OUT 0
 *
 */
int contains(Polygon g,Point p){
	int n = g.size();
	bool x = false;
	for(int i = 0; i < n; i++){
		Point a = g[i]-p,b = g[(i+1)%n]-p;
		if(abs(cross(a,b)) < EPS && dot(a,b) < EPS)return 1;
		if(a.y > b.y)swap(a,b);
		if(a.y < EPS && EPS < b.y && cross(a,b) > EPS) x = !x;
	}
	return (x ? 2:0);
}

void func(){

	for(int i = 0; i < num_section; i++){
		info[i].value = 0; //断片内のアーモンドの個数
		info[i].polygon.clear();
	}

	pre_L.x = 0;
	pre_R.x = W;

	pre_L.y = 0;
	pre_R.y = 0;

	L.x = 0;
	R.x = W;

	for(int i = 0; i < num_section; i++){

		scanf("%lf %lf",&L.y,&R.y);

		//左下から反時計回りに点を記録
		info[i].polygon.push_back(pre_L);
		info[i].polygon.push_back(pre_R);
		info[i].polygon.push_back(R);
		info[i].polygon.push_back(L);

		info[i].min_y = min(pre_L.y,pre_R.y);
		info[i].max_y = max(L.y,R.y);

		info[i].S = (((L.y-pre_L.y)+(R.y-pre_R.y))*W)/2.0; //台形の面積

		pre_L = L;
		pre_R = R;
	}

	//アーモンドの処理
	Point tmp;
	int left,right,m;
	int min_index,max_index;

	for(int loop = 0; loop < num_almond; loop++){

		scanf("%lf %lf",&tmp.x,&tmp.y);

		//アーモンドが所属し得る最小のインデックスを求める
		left = 0,right = num_section-1,m = (left+right)/2;
		min_index = num_section-1;

		while(left <= right){
			if(info[m].max_y > tmp.y){

				min_index = m;
				right = m-1;

			}else{

				left = m+1;

			}
			m = (left+right)/2;
		}

		//アーモンドが所属し得る最大のインデックスを求める
		left = 0,right = num_section-1,m = (left+right)/2;
		max_index = 0;

		while(left <= right){

			if(info[m].min_y < tmp.y){

				max_index = m;
				left = m+1;

			}else{

				right = m-1;
			}
			m = (left+right)/2;
		}

		if(min_index > max_index)continue;

		for(int i = min_index; i <= max_index; i++){

			if(contains(info[i].polygon,tmp) == 2){ //問題仕様上、ONは無いはず
				info[i].value++;
				break;
			}
		}
	}

	//累積和テーブルを作成する
	ruiseki_S[0] = info[0].S;
	ruiseki_value[0] = info[0].value;

	for(int i = 1; i < num_section; i++){
		ruiseki_S[i] = info[i].S;
		ruiseki_S[i] += ruiseki_S[i-1];
		ruiseki_value[i] = info[i].value;
		ruiseki_value[i] += ruiseki_value[i-1];
	}

	total_S = H*W;
	int ans = num_almond;

	double tmp_S;
	int tmp_almond;

	for(int i = 0; i < num_section; i++){
		/*★シータの面積は大きいほど良い★*/

		//2分探索で、残チョコの面積がS以上となる、最大の上端を求める
		left = 0,right = num_section-1,m = (left+right)/2;

		while(left <= right){
			//シータの面積を求める
			if(i != 0){

				tmp_S = ruiseki_S[m]-ruiseki_S[i-1];

			}else{

				tmp_S = ruiseki_S[m];
			}

			if(total_S-tmp_S >= need_S){ //残りがneed_S以上

				if(i != 0){

					tmp_almond = ruiseki_value[m]-ruiseki_value[i-1];

				}else{

					tmp_almond = ruiseki_value[m];
				}

				ans = min(ans,num_almond-tmp_almond);

				left = m+1;

			}else{
				right = m-1;
			}
			m = (left+right)/2;
		}
	}
	printf("%d\n",ans);
}

int main(){

	while(true){
		scanf("%d %d %lf %lf %lf",&num_almond,&num_section,&W,&H,&need_S);
		if(num_almond == 0 && num_section == 0)break;

		func();
	}
	return 0;
}


```