← 返回题目列表

AtCoder · abc015_4

D. 高桥君的痛苦

中文机器翻译题面 查看原题

問題文

Takahashi 的任务是将屏幕截图粘贴到电子表格中,作为软件按预期工作的证据。 屏幕截图是 有 N 张,高度相同但宽度不同。 此外,可以粘贴到电子表格软件中的屏幕截图包括 2 有两个限制。

  1. 电子表格软件的宽度为 W 只有一个。因此,粘贴屏幕截图的总宽度为 必须小于或等于 W 。
  2. 电子表格软件是 我无法粘贴超过 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 。