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

AT_abc228_h.[ABC228H] Histogram

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

给定一个长度为 NN 的整数序列 A=(A1,…,AN)A = (A_1, \dots, A_N) 和 C=(C1,…,CN)C = (C_1, \dots, C_N)。

你可以进行任意次数（可以为 00 次）如下操作：

  • 选择一个满足 1≤i≤N1 \leq i \leq N 的整数 ii，将 AiA_i 的值加 11。此时需要支付 CiC_i 日元的费用。

在进行任意次数操作后，设 AA 中元素的种类数为 KK，你还需要支付 K×XK \times X 日元。

请问你最少需要支付多少日元？

输入格式

输入以以下格式从标准输入读入。

NN XX
A1A_1 C1C_1
⋮\vdots
ANA_N CNC_N

输出格式

输出表示答案的数值。

输入输出样例

  • 输入#1

    3 5
3 2
2 4
4 3

    输出#1

    12

  • 输入#2

    1 1
1 1

    输出#2

    1

  • 输入#3

    7 7
3 2
1 7
4 1
1 8
5 2
9 8
2 1

    输出#3

    29

说明/提示

限制条件

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤X≤1061 \leq X \leq 10^6
  • 1≤Ai,Ci≤106(1≤i≤N)1 \leq A_i, C_i \leq 10^6 \quad (1 \leq i \leq N)
  • 所有输入均为整数。

样例解释 1

将 A1A_1 加 11 后，AA 的元素种类数为 22，总支付金额为 C1+2×X=12C_1 + 2 \times X = 12 日元。无法再减少支付金额。

由 ChatGPT 4.1 翻译

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

首页