题目描述

FlexEth 技术是一种时分复用的网络技术，能够将物理带宽按照时隙进行分配，任务是根据给定的客户业务带宽需求，在总带宽范围内分配尽可能多的时隙，最大限度地减少未分配的带宽。

约束条件：

• 1G 的子时隙只能分配在 5G 主时隙下，不可跨时隙。
• 如果客户的带宽需求大于等于 5G，则分配的带宽必须是 5G 的整数倍。
• 每个时隙只能被一个客户占用。

输入：

题目内容

问题背景

灵活以太$(FlexEth)$技术是一种时分复用的网络技术，该技术通过将物理带宽按照时间进行分片，每个时间片对应一定的接口带宽，每个客户占用一定数量的时间片，实现客户带宽的灵活分配。时间片在标准上称为时隙，支持$5G$和$1G$两种时隙粒度，我们称$5G$为主时隙，$1G$为子时隙，客户业务可分配的带宽是时隙粒度带宽的整数倍。比如我们可以将$50GE$的物理带宽按照$5G$时隙粒度分成$10$个时隙，这些时隙可以分配给多个客户使用，每个客户按照业务带宽需求可以分配多个时隙。

限制一:$1G$子时隙粒度不能跨$5G$分配。

举例$1$:客户业务带宽需求为$2G$，分配"$0[0,1]$“或者"$0[1,4]$”都是合法的,分配"$0[0]$,$1[0]$”则是非法的。

说明:我们使用$x0,x1[y0,y1,...]$这种方式来表达时隙位置信息,$x$表示主时隙编号(从$0$开始)，$y$表示子时隙编号($0$~$4$)。

$x1[y1,y2]$表示$x1$主时隙下的$y1$和$y2$两个子时隙，占用的带宽为$2G$。

限制二:如果客户需求的带宽大于等于$5G$，则只能分配$5G$的整数倍带

举例$2$:客户业务带宽需求为$6G$，分配"$0,1$"或者"$1,9$"都是合法的，分配"$0,1[0]$"则是非法的。

限制三:同一个时隙只能被一个客户业务占用。

编程要求

请实现一种时隙分配算法，为给定的客户业务带宽需求分配时隙，使得未成功分配时隙的客户业务带宽之和最小。

输入描述

输入格式:分三行输入

第一行:客户业务数量$N$，取值范围:$1<=N<=20$.

第二行:客户业务带宽列表$L$，数量和业务数一致，业务带宽取值范围: $0 <L[i]<=B$。

第三行:端口带宽$B$，取值范围$50、100、200$。

说明:带宽单位都是$Gbps$。

输出描述

输出成功分配时隙的客户业务占用的时隙带宽之和，如果没有成功分配时隙的客户，则输出$0$。

名词解释:这里的时隙带宽指的是时隙占用的带宽。

样例1

输入

9
1 3 6 10 30 21 1 2 2
100

输出

84 

说明

输出$84$表示这$9$个客户业务占用的时隙带宽之和。其中，各个客户业务的可能的时隙分配如下: $client[0]=0[0]$

$client[1]=0[1,2,3]$

$client[2]=1,2$

$client[3]=3,4$

$client[4]=5,6,7,8,9,10$

$client[5]=11,12,13,14,15$

$client[6]=16[0]$

$client[7]=16[1,2]$

$client[8]=16[3,4]$

样例2

输入

9
1 3 6 10 30 21 1 2 2
50

输出

49

说明

按照如下分配方案，可以计算得到分配的时隙带宽之和为$49$: $client[0]=0[0]$

$client[1]=0[1,2,3]$

$client[2]=failed$

$client[3]=1,2$

$client[4]=4,5,6,7 8,9$

$client[5]=failed$

$client[6]=3[0]$

$client[7]=3[1,2]$

$client[8]=3[3,4]$