Problem:


Problem F: Cutting a Chocolate

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.

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.

Sample 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

Sample output

1
1
0
1
2



Sample 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


Sample output:
1
1
0
1
2

Submission status: Accepted

Solution code:
# AOJ 1067 Cutting a Chocolate
# Python3 2018.7.10 bal4u

from bisect import bisect_left

while True:
	n, m, w, h, S = map(int, input().split())
	if n == 0: break
	m, wh2 = m+1, 2*(w*h)
	S = wh2-2*S
	tbl, s = [[0,0,0,0]], [0]
	for i in range(1, m):
		l, r = map(int, input().split())
		tbl.append([l, r, 0, r-l])
		s.append((l+r)*w)
	p = []
	for i in range(n):
		x, y = map(float, input().split())
		p.append((x, y))
	p.sort(key=lambda x:(x[1],x[0]))
	j = 1
	for i in range(n):
		x, y = p[i]
		while True:
			y1 = tbl[j-1][3]*x/w + tbl[j-1][0]
			y2 = tbl[j  ][3]*x/w + tbl[j  ][0]
			if y1 < y:
				if y < y2: break
				j += 1
			else: j -= 1
		tbl[j][2] += 1
	for i in range(1, m): tbl[i][2] += tbl[i-1][2]
	if S == 0:
		print(n)
		continue
	elif S == wh2:
		print(0)
		continue
	j = bisect_left(s, S, 0, m)
	if s[j] != S: j -= 1
	ans, i = tbl[j][2], 1
	while j+1 < m:
		j += 1
		while s[j]-s[i] > S: i += 1
		ans = max(ans, tbl[j][2]-tbl[i][2])
	print(n - ans)

Submission status: Accepted

Solution code:
# AOJ 1067 Cutting a Chocolate
# Python3 2018.7.10 bal4u

from bisect import bisect_left

while True:
	n, m, w, h, S = map(int, input().split())
	if n == 0: break
	m, wh2 = m+1, 2*(w*h)
	S = wh2-2*S
	tbl, s = [[0,0,0]], [0]
	for i in range(1, m):
		l, r = map(int, input().split())
		tbl.append([l, r, r-l])
		s.append((l+r)*w)
	p = []
	for i in range(n):
		x, y = map(float, input().split())
		p.append((y, x))
	if S == 0:
		print(n)
		continue
	elif S == wh2:
		print(0)
		continue
	p.sort()
	j, a = 1, [0]*m
	for i in range(n):
		y, x = p[i]
		while True:
			y1 = tbl[j-1][2]*x/w + tbl[j-1][0]
			y2 = tbl[j  ][2]*x/w + tbl[j  ][0]
			if y1 < y:
				if y < y2: break
				j += 1
			else: j -= 1
		a[j] += 1
	for i in range(1, m): a[i] += a[i-1]

	j = bisect_left(s, S, 0, m)
	if s[j] != S: j -= 1
	ans, i = a[j], 1
	while j+1 < m:
		j += 1
		while s[j]-s[i] > S: i += 1
		ans = max(ans, a[j]-a[i])
	print(n - ans)