TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

100.0% (27/27)

Submission's AC Ratio

48.2% (40/83)

Tags

Description

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

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

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

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

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

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

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

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

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

Input Format

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

每筆資料的:

第一行有一個數字 $n$ ,代表有幾種屬性($0 < n \leq 1000$)

第二行有 $n$ 個數字,$b_i$ 代表一個組合包有多少顆第 $i$ 種子彈($1 \leq b_i \leq 1000$)

第三行有一個數字 $k$ 代表一顆『闇』子彈需要多少個子彈才能製成($1 \leq k \leq 10000$)

第四行有 $n$ 個數字,$a_i$ 代表你需要多少顆第i種子彈($ a_i \leq 2 ^ {30} $)

第五行有一個數字 $m$ 代表你需要多少顆『闇』子彈($ m \leq 2 ^ {30} $)

Output Format

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

Sample Input 1

3
2 2 2
3
3 3 3
1

Sample Output 1

2

Hints

Problem Source

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

2021.02.09 Update: Added $\LaTeX$ by FHVirus

Subtasks

No. Testdata Range Score
1 0 50
2 1 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1
1 2000 65536 262144 2