[CTSC2005]合并正方形combine

一个二维平面初始为空，现有一系列向平面中加入点的命令。加入的点分为 $A$ 类点和 $B$ 类点。 $A$ 类点一定位于 $x$ 轴上，且任意两个 $A$ 类点不会重合； $B$ 类点可以出现在平面上的任意位置，也可以相互重合。每个 $B$ 类点都有一个权值 $W$ 。

对于当前平面上的所有 $A$ 类点，首先在每两个相邻的 $A$ 类点之间构造一个边与 $x$ 轴成 $45$ 度角的正方形。之后，每次可以将任意两个有公共点的正方形合并成一个大正方形，原来的两个小正方形随之消失。每进行一次合并，由 $A$ 类点形成的正方形数量就会减少 $1$ ，直到只剩下一个正方形。

设某个正方形在 $x$ 轴上的左、右顶点坐标分别为 $a$ 、 $b$ ，其中 $a<b$ 。对于平面上的点 $(x,y)$ ，定义

u=x-y,\qquad v=x+y。

该正方形的内部满足

a<u<b,\qquad a<v<b。

合并后的正方形将平面划分为 $9$ 个区域。与正方形的 $4$ 条边相邻的 $4$ 个区域分别为：

区域 I： $u<a$ 且 $a<v<b$ ；
区域 II： $v<a$ 且 $a<u<b$ ；
区域 III： $u>b$ 且 $a<v<b$ ；
区域 IV： $v>b$ 且 $a<u<b$ 。

区域 I、II、III、IV 中所有 $B$ 类点的权值和依次记为 $w_1$ 、 $w_2$ 、 $w_3$ 、 $w_4$ 。正方形内部，即满足 $a<u<b$ 且 $a<v<b$ 的所有 $B$ 类点的权值和记为 $w_5$ 。保证 $B$ 类点不会出现在上述区域的边界上。

本次合并的费用为

w_1+2w_2+3w_3+4w_4+5w_5。

位于其他区域的 $B$ 类点不计入本次合并费用。每次合并都不会改变 $B$ 类点的位置及其权值。合并总费用为所有合并操作费用之和，不同的合并顺序可能产生不同的总费用。

所有点按照命令顺序逐个加入平面。加入第 $i$ 个 $A$ 类点后，平面上共有 $i$ 个 $A$ 类点，以及在此之前加入的所有 $B$ 类点。设此时完成全部合并所需的最小总费用为 $f(i)$ 。

给定费用限制 $L$ ，请求出 $A$ 类点数目的最大值 $K$ ，使得前 $K$ 个 $A$ 类点对应的最小合并费用不超过 $L$ ，即 $f(K)\le L$ 。

输入格式

第一行包含两个数 $M$ 、 $L$ ，分别表示加入点的命令数和费用限制。

接下来 $M$ 行，每行描述一条加入点的命令。

若该行以字符 A 开头，则后面包含一个数，表示该 $A$ 类点的 $x$ 坐标。

若该行以字符 B 开头，则后面包含三个数，依次表示该 $B$ 类点的 $x$ 坐标、 $y$ 坐标和权值 $W$ 。

所有点的坐标均为整数。 $B$ 类点的权值 $W$ 为非负数。 $L$ 和 $W$ 均为十进制数，小数部分不超过 $3$ 位。

输出格式

输出一个整数 $K_{\max}$ ，表示满足 $f(K)\le L$ 的最大 $K$ 。

样例输入

8 30.0
A -2
A 0
B 7 8 5.0
B 4 -3 2.0
B -3 4 1.0
A 2
B -4 5 1.0
A 4

样例输出

样例解释

前 $3$ 个 $A$ 类点的最小合并费用为 $f(3)=27$ ，前 $4$ 个 $A$ 类点的最小合并费用为 $f(4)=36$ 。

由于 $f(3)<30$ ，而 $f(4)>30$ ，因此满足要求的最大 $K$ 为 $3$ 。

数据范围

所有 $A$ 类点和 $B$ 类点的坐标均为整数；
$B$ 类点的权值满足 $W\ge 0$ ；
$L$ 和 $W$ 均为十进制数，小数部分不超过 $3$ 位。

来源与许可

本题为 CTSC 2005 试题「合并正方形」，题面与测试数据整理自 BZOJ。

样例 1

输入

8 30.0
A -2
A 0
B 7 8 5.0
B 4 -3 2.0
B -3 4 1.0
A 2
B -4 5 1.0
A 4