丝路货架

2026 信息素养大赛复赛卷（卷二·丝路新城） 第 12 题

题目描述

李莳花在丝绸之路的集散中心管理一个货架，用于摆放来自西域各国的精美瓷器。货架每层的总宽度固定为 W，为保证摆放有序，所有摆件必须严格按照输入顺序依次摆放。

• 每个摆件有固定宽度 $w_i$ 和高度 $h_i$。
• 摆件只能横向并排摆放，同一层总宽度不能超过货架宽度 W。
• 如果当前层剩余宽度不足以放下下一个摆件，必须另起一层摆放。
• 每一层的最终高度由该层最高摆件的高度决定。
• 整个货架的总高度为每一层高度之和。

请你编程计算：按规则摆完所有瓷器后，货架所需的最小总高度。

输入格式

第一行两个整数 n, W，分别表示摆件数量和货架每层宽度。

接下来 n 行，每行两个整数 $w_i, h_i$，依次表示每个摆件的宽度和高度。

输出格式

输出一个整数，表示货架的总高度。

样例输入

5 5
2 1
1 2
1 3
2 3
2 2

样例输出

6

样例说明

• 第一层：摆件 1+2+3，宽度 = 2+1+1 = 4，最大高度 = 3。
• 第二层：摆件 4+5，宽度 = 2+2 = 4，最大高度 = 3。
• 总高度 = 3 + 3 = 6。

注：原卷"样例输出"误写为 5，与其"样例解释"（3+3=6）矛盾。依照题意与解释，正确答案应为 6，本处已更正。

数据范围

• 1 ≤ n ≤ 100
• 1 ≤ $w_i$ ≤ W ≤ 1000
• 1 ≤ $h_i$ ≤ 100