カメのシータとベーコは二人でチョコレートを分け合うことにした。 チョコレートは長方形である。チョコレートの角は (0,0) , (w,0) , (w,h) , (0,h) にある。 チョコレートは綺麗に割るために切り込みが入っている。 二匹はこの切り込みに沿ってのみチョコレートを切ることにした。
(0,0)と(0,h)を結ぶ線分上と (w,0) と (w,h) を結ぶ線分上に m 個の点があり、それぞれy座標が小さいほうから数えてi番目の点同士を結んだものが切り込みとする。 これらの線分はx座標が0 < x < w となる区間でで交わることは無い。ただしx=0 または x= w で同じ点を共有することはある。 ただし (0,li)=(0,lj) かつ (w,ri)=(w,rj) なら i=j である。
切り込みによって分けられるチョコレートにはそれぞれ番号をつけることができる。 (0,0) , (0,l0) , (w,r0) , (w,0) から構成されるピースは0, (0,li-1) , (0,li) , (w,ri) , (w,ri-1) から構成されるピースには i (0 < i < m ) の番号を割り当てる。 詳しくは図を見て欲しい。
チョコレートには n 個の特別な味がするがとても高カロリーなアーモンドが含まれている。 アーモンドは円であるが半径は無視できるほど小さい。 アーモンドの位置は (x,y) であらわされる。
二匹のカメはとてもわがままで以下の要求が満たされる切り方を求めている。
シータの要求は、チョコレートが連続した1つのピースであることである。 ただしシータの取り分が 0 であることもある。 彼女の持っているチョコレートの中で最小のピース番号を i , 最大のピース番号を k とする。 この時彼女は i から k までのピースすべてを持っていないといけない。 先程の図でもしシータのチョコレートが1,2,3となったらそれは連続している。 1,3や0,2,4 は連続していないといえる。
ベーコの要求はチョコレートの面積を S 以上にすることである。 またベーコは体重を気にしているのでチョコレートの上にあるアーモンドの数はできるだけ少ないほうがいいと考えている。
このチョコレートはとても高級なので二匹はすべてのピースを余さないで分けなければいけない。
あなたの仕事は二匹の要求を満たすような切り方をしたときに、ベーコの取り分になるアーモンドの数を最小にすることである。
入力は複数のケースからなる。 各ケースは以下のフォーマットで与えられる。
n m w h S l0 r0 ・・・ lm-1 rm-1 x0 y0 ・・・ xn-1 yn-1
入力の最後は5つの 0 からなる n はアーモンドの総数、 m はチョコレート上の区間の数、 w はチョコレートの幅、 h はチョコレートの高さ、 S はベーコの要求するチョコレートの面積、をそれぞれ表す。 xi yi 以外の入力は整数で与えられる。
また各値は以下の条件を満たす
1 ≤ n ≤ 30000
1 ≤ m ≤ 30000
1 ≤ w ≤ 200
1 ≤ h ≤ 1000000
0 ≤ S ≤ w*h
i < j なら li ≤ lj 、 ri ≤ rj となる。また i 番目の線分と j 番目の線分は多くとも1点しか共有しない。 また(lm-1, rm-1)は( h , h ) になることが保証されている xi ,yi は小数点以下10桁からなる値であり、必ず (0,0) と (w,h) からなる長方形に含まれている。 また各点は全ての線分から少なくとも 0.00001 以上離れている。
ベーコの取り分になるアーモンドの数を1行に出力する。
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
1 1 0 1 2