A36456.废品回收

时间限制：1000ms，内存限制：128MB

lucy 的老师为了倡导废品回收，给大家布置了一项作业：利用有限的空间回收最有价值的 $k$ 件废品（即件数 $\le k$ ）。然而，这些废品也是分种类的，它们共有 $A, B$ 两种类型，而 $k$ 件废品是指在 $A, B$ 两种中各拿 $k$ 件。

现在 lucy 共收集了 $A,B$ 两种废品共 $n$ 件，它们的处理后价值是 $v_i$，其处理价格为 $p_i$。现在请你帮她求出她的最优拿取结果价值。

输入共 $n + 1$ 行：
第一行为两个整数 $n, k$ ，表示 $A, B$ 两种废品的总数量和需要拿取的废品数量；
接下来 $n$ 行，每行 $1$ 个字符 $k_i$，表示废品种类；后接 $2$ 个正整数 $v_i$ 和 $p_i$ ，分别表示处理后的价值和处理价格。

输出仅一行一个整数，表示 $A, B$ 种类废品各拿取 $k$ 件后的最优结果价值。

【数据范围】

对于 $100\%$ 的数据，保证 $1 \le n \le 1000 ， 1\le k \le 500$

测试点编号	数据范围	特殊性质
$1$~$5$（对于 $50\%$ 的数据）	$1 \leq v_i,p_i \leq 10^5$	性质 A
$6$~$10$（对于 $100\%$ 的数据）	$1 \leq v_i,p_i\leq 10^5$	无

性质 A：保证 $p_i \le v_i$

数据保证 $A,B$ 类物品的数量一定大于等于 $k$，$k_i$ 是字符 A 或 B。

【样例解释】

样例组 #1：最优拿取方式为：
$A$ 类：拿取第 $1$ 和 $3$ 件物品；
$B$ 类：拿取第 $2$ 和 $4$ 件物品；
最终价值：$(100 - 2) + (100 - 4) + (100 - 3) + (100 - 9) = 382$。