SP1871 MKBUDGET - Making A Budget

一家公司利用临时员工来应对不稳定的工作量，以此避免支付正式员工的福利。然而，他们需要为每个临时员工向职业介绍所支付一笔固定费用，同时在解雇时支付固定的遣散费，当然，还有每月的工资。公司对何时需要临时工以及每月所需人数有清晰的预期。根据提供给职业介绍所的费用、临时工的月薪和遣散费，可以通过适当保留临时员工，来降低总体成本，特别是在未来还需用到这些员工时。 考虑一个例子：假如公司在三月需要 10 名临时工，四月需要 9 名，而五月需要 11 名。临时工每月薪水为 500 美元，职业介绍所每招聘一人收取 400 美元，解雇一个员工支付 600 美元的遣散费。如果公司仅雇佣所需的最少人数，他们需支付如下费用（不包括最后一个月结束时解雇员工的费用）：  公司的总费用为 20,400 美元。然而，如果他们在三月底不解雇多余的临时工，而继续雇用至五月底，他们将节省 400 美元的招聘费和 600 美元的遣散费，仅需支付 500 美元的工资，总体节省 500 美元。 在这个问题中，根据输入的数据，你需要计算公司为了满足每个月最少的员工需求所需的最低总成本。不考虑第一个月前的员工和最后一个月后的遣散费。假设规划期不超过 24 个月，且每项费用均大于 0。

输入包含多组测试数据。每组数据以一个整数 $N$ 开始，表示规划的月份数（最多 24 个月）。接下来三个整数分别为员工的招聘费用、月薪和遣散费。最后是 $N$ 个整数，表示每个月所需的最少员工人数。输入以一个 0 作为结束标记。

对于每组输入数据，输出案例编号（1, 2, …）和公司的最低成本。请使用示例中的格式进行输出。

- $1 \leq N \leq 24$ - 雇佣成本、月薪以及遣散费均大于 0 - 每个月所需的最低员工人数不小于 0 **本翻译由 AI 自动生成**