题目详情题解（0）讨论（0）提交记录（0）

AT_past202104_n.活動

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 nn 个物品，每个物品都有两个参数：aia_i 和 bib_i。你可以按照任意顺序选择其中的一个或更多个物品。每次只能选一个，同一物品不可多次选择。

你有一个参数 hh。在开始时，你的反馈值为 00。每次，当你选择一个原始序号为 ii 的物品时，你的反馈值会增加 ai×ha_i \times h，然后 h←h−bih\larr h-b_i。允许 h<0h<0。

求出你最后能获得的最大反馈值。

输入格式

第一行输入两个整数 n,hn,h。

剩余 nn 行，每行输入两个整数 ai,bia_i,b_i。

输出格式

输出一行一个整数，答案。

输入输出样例

  • 输入#1

    4 6
4 1
3 2
2 3
1 4

    输出#1

    45

  • 输入#2

    4 6
1 1
2 2
3 3
4 4

    输出#2

    30

  • 输入#3

    16 100
18 17
5 18
7 2
5 8
6 2
16 16
2 18
13 17
18 10
11 10
17 8
1 2
20 7
4 11
7 15
2 1

    输出#3

    9282

说明/提示

数据规模与约定

对于 100%100\% 的数据，保证：

  • 1≤n≤1001 \le n \le 100，1≤h≤1051 \le h \le 10^5；
  • 1≤ai,bi≤1051 \le a_i,b_i \le 10^5。

输入解题思路，AI测评打分。不知道怎么写?

首页