Problem Statement

出處: APCS 2024 10月

Author: median

有一個杯子，可將其體積視為由兩個長方體組成（如下圖），下方的長方體底面積為$w_1\times w_1\ cm^2$，高為 $h_1\ cm$，上方的長方體底面積為$w_2\times w_2\ cm^2$，高為$h_2\ cm$cm。

一開始杯子為空。要裝$n$次飲料，每一次裝$v\ cm$容量的飲料，當水杯滿時水位不再上升。問這次倒飲料中水位上升變化量最高是幾$cm$。

Input

第一行有一個正整數$n (1 \le n \le 10)$代表要裝$n$次飲料。接下來一行有 $4$ 個正整數$w_1, w_2, h_1, h_2 (1 \le w_1, w_2, h_1, h_2 \le 50)$代表杯子的寬度與高度。最後一行有$n$個正整數代表每次裝飲料的容量。保證每次水位上升都是整數。

• (60%) n = 1，即答案為倒水後的高度
• (40%) 無限制

Output

輸出這$n$次倒水中，上升變化量最大的高度為何。

Example

1
4 6 8 5
200

10

2
5 10 12 8
400 600

13

5
16 44 28 17
2560 1280 1536 1024 10448

10