题目内容

富春包子被誉为扬州包子的“天花板”, 前来购买的顾客络绎不绝。

大厅中有 $n$ 位顾客等待叫号 (按顾客到大厅取号的顺序, 第一个取号的是第 $0$ 位, 以此类推.. (最多 $101$ 位顾客, 且不会有新顾客到来) ) ;

包子铺有 $m$ 个窗口, 每个窗口每次服务一位顾客, 服务时长 $1$ 秒; 当有多个窗口空闲时, 会从大厅队伍中同时叫号, 不会让窗口空闲 (比如大厅有 $3$ 个人, 空着 $2$ 个窗口, 会从大厅中叫前 $2$ 个人分配到空闲窗口) , 且系统会优先分配编号最小的窗口;

每位顾客一次只能买一笼包子, 如果他已买到想要的包子笼数, 会直接离开大厅; 如果还想买更多, 需回到大厅重新取号, 取号后排到等待叫号的顾客末尾。

给你一个整数数组 $baskets$, 数组长度为 $n$, $baskets[i]$ 是第 $i$ 位顾客想要购买包子的笼数。请计算出在大厅中排在第 $k$ 位的顾客购买完所有包子时, 其花费的总时间 (秒)。

输入描述

第一行: 购买包子列表 $baskets$, 列表中每个元素表示顾客计划购买的包子笼数 ($1 \le baskets[i] \le 100$, 顾客数量 $n$ 的约束条件为 $0 < n \le 101$) , 以空格隔开

第二行: 在大厅中排在第 $k$ 位的顾客 (下标从 $0$ 开始, $0 \le k < n$)

第三行: 窗口数量 $m$ ($0 < m \le 10$)

输出描述

大厅中排在第 $k$ 位 (下标从 $0$ 开始) 的顾客完成其想要购买包子所需的总时间 (秒)

样例1

输入

2 1 2
2
2

输出

3

说明

为方便理解, $C0$ ($2$) 表示首位客户需要买包子 $2$ 笼, 以此类推。大厅中队伍初始为 $\{C0 (2) ,C1 (1)，C2 (2)\}$,

开始分配:

窗口 $1$ 分配给 $C0$ (需求: $2$ 笼)

窗口 $2$ 分配给 $C1$ (需求: $1$ 笼)

大厅: $\{C2(2)\}$

窗口: 窗口 $1$:$C0(2)$, 窗口 $2$:$C1(1)$

$1$s 后:

$C0$ 买完一笼, 剩余 $1$ 笼, 回到大厅

$C1$ 完成购买, 离开

窗口 $1$ 分配给 $C2$(需求:$2$ 笼)

窗口 $2$ 分配给 $C0$(需求:$1$ 笼)

大厅: $\{\}$

窗口: 窗口 $1$:$C2(2)$, 窗口 $2$:$C0(1)$

$2$s 后:

$C2$ 买完一笼, 剩余 $1$ 笼, 回到大厅

$C0$ 完成购买, 离开

窗口 $1$ 分配给$C2$(需求:$1$ 笼)

大厅: $\{\}$

窗口: 窗口 $1$:$C2(1)$, 窗口 $2$: 空

$3$s 后:

目标顾客 $C2$ 完成购买!

总耗时:$3$ 秒

样例2

输入

5 3 3 1 4
2
3

输出

4

说明

为方便理解, $C0$ ($5$) 表示首位客户需要买包子 $5$ 笼, 以此类推。大厅中队伍初始为 $\{C0(5),C1(3),C2(3),C3(1),C4(4)\}$

开始分配:

窗口 $1$ 分配给 $C0$(需求:$5$ 笼)

窗口 $2$ 分配给 $C1$(需求:$3$ 笼)

窗口 $3$ 分配给 $C2$(需求:$3$ 笼)

大厅: $\{C3(1),C4(4)\}$

窗口: 窗口 $1$:$C0(5)$, 窗口 $2$:$C1(3)$, 窗口 $3$:$C2(3)$

$1$s 后:

$C0$ 买完一笼, 剩余 $4$ 笼, 回到大厅

$C1$ 买完一笼, 剩余 $2$ 笼, 回到大厅

$C2$ 买完一笼, 剩余 $2$ 笼, 回到大厅

窗口 $1$ 分配给 $C3$(需求:$1$ 笼)

窗口 $2$ 分配给 $C4$(需求:$4$ 笼)

窗口 $3$ 分配给 $C0$(需求:$4$ 笼)

大厅: $\{C1(2),C2(2)\}$

窗口: 窗口 $1$:$C3(1)$, 窗口 $2$:$C4(4)$, 窗口 $3$:$C0(4)$

$2$s 后:

$C3$ 完成购买, 离开

$C4$ 买完一笼, 剩余 $3$ 笼, 回到大厅

$C0$ 买完一笼, 剩余 $3$ 笼, 回到大厅

窗口 $1$ 分配给 $C1$(需求:$2$ 笼)

窗口 $2$ 分配给 $C2$(需求:$2$ 笼)

窗口 $3$ 分配给 $C4$(需求:$3$ 笼)

大厅: $\{C0(3)\}$

窗口: 窗口 $1$:$C1(2)$, 窗口 $2$:$C2(2)$, 窗口 $3$:$C4(3)$

$3$s 后:

$C1$ 买完一笼, 剩余 $1$ 笼, 回到大厅

$C2$ 买完一笼, 剩余 $1$ 笼, 回到大厅

$C4$ 买完一笼, 剩余 $2$ 笼, 回到大厅

窗口 $1$ 分配给 $C0$(需求:$3$ 笼)

窗口 $2$ 分配给 $C1$(需求:$1$ 笼)

窗口 $3$ 分配给 $C2$(需求:$1$ 笼)

大厅: $\{C4(2)\}$

窗口: 窗口 $1$:$C0(3)$, 窗口 $2$:$C1(1)$, 窗口 $3$:$C2(1)$

$4$s 后:

$C0$ 买完一笼, 剩余 $2$ 笼, 回到大厅

$C1$ 完成购买, 离开

目标顾客 $C2$ 完成购买!

总耗时:$4$ 秒