思路

• 将鞋按尺码分组（共有 $15$ 种尺码：$35\sim49$）。

• 对每个尺码：

  • 先按颜色尽可能配对左/右同色对，得到价值 $p$ 的配对（贪心成立因为 $p \ge q$）。
  • 剩余的左鞋总数与右鞋总数取最小值，做异色配对，得到价值 $q$ 的配对。

• 复杂度：时间 $O(n)$，空间 $O(n)$。

题目内容

小明家里有 $n$ 只鞋，他想出售这些鞋。

每只鞋区分左右，包含尺码，颜色两个属性、只有尺码相同的左鞋和右鞋凑成一双鞋才能够出售。

当两只鞋子的颜色相同时，一双鞋可以卖 $p$ 元，不相同时只能卖 $q$ 元。

小明想知道他家里这些鞋最多能卖多少元。

输入描述

输入第一行有三个正整数 $n(1≤n≤10^5)、p(1≤p≤100)$ 和 $q(1≤q≤p)$ ，分别表示鞋子的总数、颜色相同时鞋子的价格以及不相同时鞋子的价格；

接下来 $n$ 行的第 $i$ 行有三个正整数 $a_i(a_i∈{0,1})、b_i(35≤b_i≤49)$ 和 $c_i(1≤c_i≤n)$，分别表示第 $i$ 鞋是左鞋还是右鞋、尺码以及颜色，当 $a_i=0$ 时，鞋子是左鞋；当 $a_i=1$ 时，鞋子是右鞋。颜色用从 $1$ 到 $n$ 的数字表示；

输出描述

输出一个正整数，表示小明卖鞋子最多能卖多少元。

样例1

输入

5 10 4
0 35 1
0 36 2
0 35 2
1 36 1
1 35 1

输出

14

说明

样例解释 第一只鞋和第五只鞋分别为左鞋和右鞋，且尺码、颜色相同，可以卖 $10$ 元；

第二只鞋和第四只鞋分别为左鞋和右鞋，尺码相同但颜色不同，可以卖 $4$ 元，总计 $14$ 元。