問題文
Takahashi 的任务是将屏幕截图粘贴到电子表格中,作为软件按预期工作的证据。 屏幕截图是 有 N 张,高度相同但宽度不同。 此外,可以粘贴到电子表格软件中的屏幕截图包括 2 有两个限制。
- 电子表格软件的宽度为 W 只有一个。因此,粘贴屏幕截图的总宽度为 必须小于或等于 W 。
- 电子表格软件是 我无法粘贴超过 K 个屏幕截图。因此,可以粘贴到电子表格软件中的屏幕截图是 最多 K 件。
此外,由于截图具有“重要性”,高桥君 2 我想在满足两个约束的同时最大化粘贴屏幕截图的总体重要性。 然而,这个任务对他来说很困难,因此找到屏幕截图的重要性值的最大总和,您可以将其粘贴到电子表格中供他使用。
入力
输入是按以下格式从标准输入给出的。
W N K A_1 B_1 A_2 B_2 : A_N B_N
- 1 电子表格软件的宽度显示在行中 给出了 W (1 ≦ W ≦ 10000) 。
- 2 行显示屏幕截图的数量。 N (1≦N≦50) 以及可以粘贴到电子表格中的屏幕截图数量 K(1≦K≦N) 用空格分隔。
- 3 从行 N 行提供有关每个屏幕截图的信息。其中 行 i 第 i 个屏幕截图中的宽度 A_i (1 ≦ A_i ≦ 1000) 和重要性 B_i (1 ≦ B_i ≦ 100) 值以空格分隔。
出力
可粘贴到电子表格软件中的屏幕截图的最大总重要性。 1 行。在输出末尾添加换行符。
入力例1
10 3 2 4 20 3 40 6 100
出力例1
140
2 第 和 如果您选择第 3 张屏幕截图,则总宽度将为 9 ,您使用的截图是 2 ,满足条件。 此时的重要性总和为 在 40 + 100 在 140 变为。
入力例2
10 5 4 9 10 3 7 3 1 2 6 4 5
出力例2
18
必须 请注意,您不必使用 K 屏幕截图。
入力例3
22 5 3 5 40 8 50 3 60 4 70 6 80
出力例3
210
即使宽度足够,截图也无法最大化。 请注意,您最多只能放置 K 。