Description

你正在经营一座摩天轮，该摩天轮共有 4 个座舱 ，每个座舱 最多可以容纳 4 位游客 。你可以逆时针轮转座舱，但每次轮转都需要支付一定的运行成本runningCost。摩天轮每次轮转都恰好转动1/4周。

给你一个长度为n的数组customers，customers[i]是在第i次轮转（下标从 0 开始）之前到达的新游客的数量。这也意味着你必须在新游客到来前轮转i次。每位游客在登上离地面最近的座舱前都会支付登舱成本boardingCost，一旦该座舱再次抵达地面，他们就会离开座舱结束游玩。

你可以随时停下摩天轮，即便是在服务所有游客之前 。如果你决定停止运营摩天轮，为了保证所有游客安全着陆，将免费进行所有后续轮转 。注意，如果有超过4位游客在等摩天轮，那么只有 4 位游客可以登上摩天轮，其余的需要等待 下一次轮转 。

• 1 <= n <= 10^5
• 0 <= customers[i] <= 50
• 1 <= boardingCost, runningCost <= 100

Input Format

第一行输入一个正整数n，表示一共有n组游客游玩摩天轮。

第二行输入n个正整数，构成数组customers, 其中customers[i]表示第i轮游客数量。

第三行输入一个正整数boardingCost，每位游客摩天轮票价 。

第四行输入一个正整数runningCost，轮转一次座舱的成本。

Output Format

输出最大化利润所需执行的最小轮转次数。 如果不存在利润为正的方案，则返回-1

2
8 3
5
6

3

Hint

【样例一解释】

1. 8 位游客抵达，4 位登舱，4 位等待下一舱，摩天轮轮转。当前利润为 4*$5 - 1*$6 = $14 。
2. 3 位游客抵达，4 位在等待的游客登舱，其他 3 位等待，摩天轮轮转。当前利润为 8*$5 - 2*$6 = $28 。
3. 最后 3 位游客登舱，摩天轮轮转。当前利润为 11*$5 - 3*$6 = $37 。轮转 3 次得到最大利润，最大利润为 $37 。

Source

信奥星OJ http://127.0.0.1