#P10505. [2021年联测]Rosenkreuzstilette

    ID: 9622 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2700省选/NOI-欧几里得算法游程编码Trie最长公共前缀栈树形 DP二分查找一维前缀和消除被支配候选

[2021年联测]Rosenkreuzstilette

题目描述

Tia 有 nn 个魔法球,第 ii 个球的能量为 eie_i,魔力值为 mim_i。魔力值大于 00 的球有魔力,魔力值小于或等于 00 的球没有魔力。

每次可以选择执行下面一种操作,操作同时作用于所有当前有魔力的球。

  • Freudia 让每个有魔力的球的魔力值减去该球的能量,即 mi←mi−eim_i\leftarrow m_i-e_i。操作费用为 aa。
  • Grolla 交换每个有魔力的球的能量和魔力值,即交换 mim_i 与 eie_i。操作费用为 bb。

求使所有魔法球都没有魔力的最小总费用。

输入格式

第一行三个整数 n,a,bn,a,b。接下来 nn 行,每行两个整数 ei,mie_i,m_i。

输出格式

一行一个整数,表示最小总费用。

样例

4 8 6
1 6
2 4
6 5
5 2
22

先使用 Freudia 的操作,使魔力值变为 [5,2,−1,−3][5,2,-1,-3]。再使用 Grolla 的操作,能量变为 [5,2,6,5][5,2,6,5],魔力值变为 [1,2,−1,−3][1,2,-1,-3]。最后再使用 Freudia 的操作,魔力值变为 [−4,0,−1,−3][-4,0,-1,-3]。总费用为 8+6+8=228+6+8=22。

数据范围

1≤n≤1051\le n\le10^5,1≤a,b≤1071\le a,b\le10^7,1≤ei,mi≤1051\le e_i,m_i\le10^5。

原赛子任务 特殊限制 原赛分值
1 n≤100n\le100,ei,mi≤20e_i,m_i\le20 30
2 ei,mi≤1000e_i,m_i\le1000
3 a=1a=1,b=107b=10^7 10
4 无 30

原 PDF 题面