X5016. 小慕的网络优化计划

在小慕负责的一个智慧城市项目中，她需要优化城市的网络覆盖能力。为了提升居民上网体验，她决定通过部署新的网络基站，让每个区域的信号覆盖更均衡。 整个城市共有 n 个区域，第 i 个区域当前已有 `cities[i]` 个基站。每个基站可以为其所在区域及其前后 r 个区域（即距离不超过 r 的区域）提供信号服务。区域是线性排列的，编号从 0 到 n-1。 现在小慕可以再部署 k 个新的基站（允许在同一区域部署多个），她希望在合理分配后，所有区域中信号覆盖最差的区域，其服务质量能够尽量高。 其中，一个区域的服务质量定义为所有能为它提供信号的基站数量。请你帮小慕计算，在最优安排下，所有区域的最小服务质量能达到多少。