TopCoder

Thumb ya2
赤ずきんチャチャ
もっと心の中を二人見せ合えたなら 答えはつかめるよ

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

55.6% (5/9)

Description

百年前的『破曉前夕』大戰,人類濫用魔法互相殘殺,慘烈的戰況激起眾神震怒,決定收回人類使用魔法的能力。

但是,被慾望蠱惑的人類發現魔法並未消失,只是無法使用,於是他們發展出將魔法灌注到子彈中,再用火槍射出魔法子彈攻擊敵人的方法,重新獲得力量。

自此,世界邁入殺戮的戰爭時代。唯一能改變世界命運的,就是傳說中的魔槍--『銃姬』。

在一次意外中,你獲得了銃姬,而你發現銃姬所能使用的子彈必須要是特別的『闇』屬性。

這個世界的魔法分成n大屬性,各自都有各自特別奧妙的地方,如『風』能治癒,『火』能攻擊…

而『闇』屬性則是一種不為人知、相當特別的一種屬性,而其子彈也無法從市面上看到,必須將k個『任一種類的元素』的子彈加以封印,才能產生『一個』『闇』屬性的子彈。

現在你需要a[i]個第i種屬性的子彈,以及m個『闇』屬性的子彈,但商店卻沒有零售子彈, 只有販售子彈組合包。

一個組合包包含了b[i]個第i種屬性的子彈(不過當然沒有包含『闇』屬性的子彈)

精打細算的你,想買越少組合包越好,你最少要買多少個組合包才能滿足你所要的條件呢?

Input Format

本題有多筆測試資料,請以EOF作為結束

每筆資料的:

第一行有一個數字n,代表有幾種屬性 (0< n<=1,000)

第二行有n個數字,ai代表一個組合包有多少顆第i種子彈 (1<=ai<=1,000)

第三行有一個數字k代表一顆『闇』子彈需要多少個子彈才能製成(1<=k<=10,000)

第四行有n個數字,bi代表你需要多少顆第i種子彈 (bi<=230)

第五行有一個數字m代表你需要多少顆『闇』子彈 (m<=230)

Output Format

對於每筆資料輸出一個數字p,代表最少要買多少包組合包才可以滿足條件

Sample Input

3
2 2 2
3
3 3 3
1

Sample Output

2

Hints

Problem Source

原TIOJ1412 / 快樂暑假營複習賽。Problem Setter:hallogameboy

Subtasks

For Testdata: 0 ~ 0, Score: 50
For Testdata: 1 ~ 1, Score: 50
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 65536 65536
1 2000 65536 65536