SP11769 RPLK - Kind and gently

吉赛尔正在装修她的房子，她的丈夫无法帮忙，所以她委托你这个任务：为她设计连接房子两层的楼梯。楼梯由 $W$ 段木头组成。吉赛尔想保持传统，要求楼梯的台阶之间有一定间隔。你需要注意，每个台阶的末端都会与下一个台阶的起始部分重叠，以此类推。吉赛尔有一个限制，她希望用不超过 $W$ 段木头来完成楼梯的建造。 如下图所示： [](http://tinypic.com?ref=14e12bk) 图中显示，两个台阶之间在高度和宽度上都有一个固定间隔。 吉赛尔希望利用 $E$ 块木头来建造楼梯，每块木头可被切割成不多于 $W$ 个台阶。你只能进行垂直切割，不能旋转木头。每个台阶的宽度必须严格为 $M+1$，其中 $M$ 是重叠部分，1 是固定脚宽。 ### 输入格式 - 输入的第一行为整数 $T$，表示有 $T$ 组测试数据。随后是 $T$ 组数据。 - 对于每组数据，首先是四个正整数 $(E, M, K, W)$，分别表示：木头数量 $E$，重叠长度 $M$，台阶间高度差 $K$，以及允许切割的最大台阶数 $W$。接下来的 $E$ 行，每行包含两个整数 $E_h$ 和 $E_w$，分别表示每段木头的高度和宽度。 ### 输出格式 - 对于每组测试数据，输出“Scenario #i: ”，其中 $i$ 是当前处理的测试序号（从 1 开始），接着是能建造的最大楼梯高度。 ### 数据范围与提示 - (1 ≤ 每块木头的宽度和高度 ≤ 1000) = $W_iH_i$ - 小规模输入 (40%) - $1 \le T \le 200$ - $1 \le E, K, M \le 100$ - $W_iH_i \le M \le 100$ - $1 \le W \le 100$ - 大规模输入 (60%) - $1 \le T \le 10$ - $1 \le E, K \le 100,000$ - $W_iH_i \le M \le 1,000$ - $1 \le W \le 10,000$ **本翻译由 AI 自动生成**

无

无