外卖店一共有 $N$ 种食物，分别用 $1$ 到 $N$ 编号。
第 $i$ 种食物有固定的价钱 $P_i$ 和保质期 $S_i$。第 $i$ 种食物会在 $S_i$ 天后过期。JYY 不会吃过期的食物。
比如 JYY 如果今天点了一份保质期为 $1$ 天的食物，那么 JYY 必须在今天或者明天把这个食物吃掉，否则这个食物就再也不能吃了。保质期可以为 $0$ 天，这样这份食物就必须在购买当天吃掉。
JYY 现在有 $M$ 块钱，每一次叫外卖需要额外付给送外卖小哥外送费 $F$ 元。送外卖的小哥身强力壮，可以瞬间给 JYY 带来任意多份食物，每种食物可以买任意多份。
JYY 想知道，在满足每天都能吃到至少一顿没过期的外卖的情况下，他可以最多宅多少天呢？
1. 将“最大天数”改写成“判定能否活到 (T)”
题目要求最大化能宅的天数。先考虑一个判定问题：给定天数 (T)，是否存在策略使得在预算 (M) 内每天都吃到至少一顿不过期外卖？
显然若能活到 (T) 天，则一定能活到 (T-1) 天，因此可行性对 (T) 单调。于是可以对 (T) 二分，关键在于实现 check(T)。
2. 把策略抽象成“下单次数 + 分段长度”
固定要活 (T) 天。每次下单（叫外卖）会付一次外送费 (F)，并买若干份饭，之后连续若干天吃完。于是整个 (T) 天可以被切成 (x) 段，第 (j) 段由第 (j) 次下单供餐，段长为 (L_j)，满足：
$$ L_1+L_2+\cdots+L_x=T. $$
单次下单最多能覆盖的天数由最长保质期决定。保质期为 (S_i) 的食物从购买当天算第 (0) 天，可吃到第 (S_i) 天，一共 (S_i+1) 天，因此
$$ L_{\max}=\max_i(S_i)+1,\qquad 1\le L_j\le L_{\max}. $$
3. 得到“最低单价函数” (c(k))
在一段中，如果连续吃 (L) 天，那么第 (k) 天（从 0 开始）吃到的那顿必须能放 (k) 天，等价于选择满足 (S_i\ge k) 的食物。
因此定义：
$$ c(k)=\min{P_i\mid S_i\ge k},\qquad k\ge 0. $$
含义：要在“买后第 (k) 天”吃一顿不过期外卖的最低单价。
性质：
- (c(k)) 单调不降（放得更久只会更贵或相等）；
- 由于只有 (N) 种食物，去掉被支配项后，(c(k)) 只会跳变 (\le N) 次（分段常数）。
4. 得到“段成本函数” (C(L))
若一次下单要覆盖连续 (L) 天，那么要买 (L) 顿：对应 (k=0,1,\dots,L-1)，每顿最少花 (c(k))，再加一次外送费 (F)。因此一次下单的最小成本为：
$$ C(L)=F+\sum_{k=0}^{L-1}c(k)\qquad(1\le L\le L_{\max}). $$
于是固定 (T) 后，“下单 (x) 次、段长为 (L_1,\dots,L_x)”的总成本就是：
$$ \sum_{j=1}^{x} C(L_j). $$
5. 关键形状：(C(L)) 离散凸 ⇒ 固定 (x) 时段长只差 1
观察差分：
$$ C(L+1)-C(L)=c(L). $$
由于 (c(L)) 单调不降，差分单调不降，因此 (C(L)) 是离散凸函数。离散凸的直接结论是：在
$$ L_1+\cdots+L_x=T $$
总和固定、(x) 固定时，使 (\sum C(L_j)) 最小的分配一定“尽量平均”，即任意两段长度差不超过 1。
令
$$ q=\left\lfloor\frac{T}{x}\right\rfloor,\qquad r=T-qx\quad(0\le r<x), $$
则最优分段一定是：(r) 段长度为 (q+1)，其余 (x-r) 段长度为 (q)。
6. 固定 (T) 与 (x) 的最小花费：定义 (G_T(x))
根据上面的分段结构，固定 (T,x) 的最小总花费为：
$$ G_T(x)=(x-r)C(q)+rC(q+1), $$
其中 (q=\lfloor T/x\rfloor,\ r=T-qx)。
在 check(T) 中，我们要判断：
$$ \min_x G_T(x)\le M\ ? $$
同时 (x) 需要满足可行范围：
- 单次最多覆盖 (L_{\max}) 天，因此至少要
$$ x\ge x_{\min}=\left\lceil\frac{T}{L_{\max}}\right\rceil; $$
- 外送费付得起且一天至多一单，因此至多
$$ x\le x_{\max}=\min\left(T,\left\lfloor\frac{M}{F}\right\rfloor\right). $$
7. 为什么在固定 (q=\lfloor T/x\rfloor) 的区间上，(G_T(x)) 是一次函数
当 (\lfloor T/x\rfloor=q) 固定时，(x) 落在一个整数区间：
$$ x\in I_q=\left[\left\lfloor\frac{T}{q+1}\right\rfloor+1,\ \left\lfloor\frac{T}{q}\right\rfloor\right]. $$
在 (I_q) 上 (q) 不变，(C(q),C(q+1)) 都是常数，而 (r=T-qx) 对 (x) 是一次函数。将
$$ G_T(x)=(x-r)C(q)+rC(q+1) $$
展开：
$$ \begin{aligned} G_T(x) &=xC(q)+r\big(C(q+1)-C(q)\big) &=xC(q)+(T-qx)\big(C(q+1)-C(q)\big) &=T,c(q)+x\big(C(q)-q,c(q)\big), \end{aligned} $$
因此在区间 (I_q) 上 (G_T(x)) 是关于 (x) 的一次函数。一次函数在区间上的最小值必在端点取得，所以对每个 (q) 只需检查 (I_q) 的端点 (lo,hi)。
8. 从“枚举所有 (q)”压到“只枚举 (O(N)) 个 (q)”
直接枚举所有可能的 (q=\lfloor T/x\rfloor) 会有 (O(\sqrt T)) 个取值，但本题还有更强结构：(c(k)) 本身只会跳变 (\le N) 次。
设 (c(k)) 的分段边界为
$$ 0=\kappa_0<\kappa_1<\cdots<\kappa_m=L_{\max},\quad m\le N, $$
并且在每段上
$$ c(k)=p_j\quad \forall k\in[\kappa_{j-1},\kappa_j-1]. $$
若 (q) 落在同一段内，即 (q\in[\kappa_{j-1},\kappa_j-1])，则 (c(q)=p_j) 恒定，且 (C(q)) 在该段内对 (q) 是线性的（每增加 1 增加 (p_j)），因此
$$ C(q)-q,c(q)=\text{常数（与 }q\text{ 无关）}. $$
于是同一价格段内的所有 (q) 会产生同一条一次函数 (G_T(x)=A+Bx)，只需要关注段边界附近即可。
实践中取候选：
$$ \text{candQ}=\Big(\bigcup_{j=1}^{m}{\kappa_j-1,\kappa_j,\kappa_j+1}\Big)\cap[1,L_{\max}], $$
大小为 (O(N))。
9. check(T) 的端点枚举实现方式
对每个候选 (q\in\text{candQ})，先算出区间端点：
$$ lo=\left\lfloor\frac{T}{q+1}\right\rfloor+1,\qquad hi=\left\lfloor\frac{T}{q}\right\rfloor. $$
把 ([lo,hi]) 与可行范围 ([x_{\min},x_{\max}]) 取交，若非空，则将交集端点加入候选集合 candX。
最后计算
$$ \min_{x\in \text{candX}}G_T(x) $$
并与 (M) 比较即可得到 check(T)。
10. 总算法
- 预处理 (c(k)) 的分段（去支配后最多 (N) 段），并做前缀和以快速计算 (C(L))；
- 对 (T) 二分；
- 在
check(T)中用第 9 节方法枚举候选 (x)，求 (\min G_T(x)\le M)。
11. 复杂度要点
- (c(k)) 分段数 (\le N)，因此候选 (q) 数为 (O(N))，候选 (x) 数也为 (O(N))；
- 每次
check(T)只计算 (O(N)) 个 (G_T(x))； - 外层二分 (T) 约 (O(\log M)) 次。
总体约为 (O(N\log M))（常数很小，(N\le 200) 时非常轻松）。