TopCoder

Thumb
柊 四千
あぅあぅ~

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

37.5% (3/8)

Description

在一片山的上空,高度為T處有N個處於不同水平位置的燈泡,如上圖所示。
如果山的邊界上某一點與第i盞燈的連線不經過任何山稜線上的一點,我們稱第i盞燈可以照亮該點。
請問至少要打開幾盞燈,才能照亮山上每一個轉折點?

Input Format

輸入可能包含多筆測試資料。

對於每筆測試資料:


第1列:一個整數M (1<=M<=100,000),代表山稜折線的轉折點個數。

第2~M+1列:Xi Hi,依序代表轉折點的水平座標以及垂直海拔高度。(-100,000<=Xi, Hi<=100,000)
所有轉折點座標將以X座標由小到大排列。

第M+2列:N T,其中N代表燈泡個數,T代表所有燈泡的高度,該高度必定高於整座山最高轉折點的高度。
(1<=N, T<=100,000)

第M+3列:有N個整數 B1 B2 ... BN,代表N個燈泡的水平座標,且依座標值由小到大排列。

Output Format

如果可以點亮某幾盞燈而照亮所有轉折點,請輸出最少需要點亮的燈泡數量。

否則請輸出 "you need more bulbs!"(不包含雙引號)。

Sample Input

6
1 1
3 3
4 1
7 1
8 3
11 1
4 5
1 5 6 10

6
1 1
3 3
4 1
7 1
8 3
11 1
2 5
1 5

Sample Output

2
you need more bulbs!

Hints

在第一筆範例測試資料中,選擇位置為1以及6的兩個燈泡,即可照亮每個轉折點。

Problem Source

原TIOJ1404 / 快樂暑假第四次練習比賽。Problem Setter:Tmt。
(Adapted From CEOI 2000 Problem 6, 算法藝術P.13)
題目修正by hiiragi4000

Subtasks

For Testdata: 0 ~ 0, Score: 12
For Testdata: 1 ~ 1, Score: 12
For Testdata: 2 ~ 2, Score: 12
For Testdata: 3 ~ 3, Score: 12
For Testdata: 4 ~ 4, Score: 12
For Testdata: 5 ~ 5, Score: 12
For Testdata: 6 ~ 6, Score: 12
For Testdata: 7 ~ 7, Score: 16
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 262144
1 10000 65536 262144
2 10000 65536 262144
3 10000 65536 262144
4 10000 65536 262144
5 10000 65536 262144
6 10000 65536 262144
7 10000 65536 262144