Description

A two-dimensional plane is initially empty. There is a sequence of commands that add points to the plane.

There are two kinds of points, called type A points and type B points (see Figure 1, where black squares denote type A points and small black dots denote type B points). Type A points always lie on the $X$-axis and never overlap, while type B points can appear anywhere on the plane and may overlap. Each type B point has a weight $W$.

Processing: (1) Initially, between every pair of adjacent type A points, draw a square whose sides make a $45$-degree angle with the $X$-axis (see Figure 2). (2) Each time, you may merge any two squares that share at least one common point into a larger square; after merging, the two smaller squares disappear. The second and third squares from the left in Figure 2 are merged and shown as the gray-edged square in Figure 3.

After merging, the resulting square divides the plane into $9$ regions. The $4$ regions adjacent to the $4$ sides of the square are labeled I, II, III, IV in Figure 3. Let $w_1$ be the sum of weights of type B points falling into region I, $w_2$ for region II, $w_3$ for region III, and $w_4$ for region IV. Let $w_5$ be the sum of weights of type B points falling inside the gray square (type B points are guaranteed not to lie on the boundaries of any region). Then the cost of this merge is $w_1 + 2 w_2 + 3 w_3 + 4 w_4 + 5 w_5$. Type B points in other regions are ignored. Each merge does not affect the positions or weights of the type B points.

Each time you perform a merge, the number of squares formed by type A points decreases by one, until only one square remains. The total merge cost is the sum of the costs of all merges. Different merge orders may result in different total costs.

Points are added to the plane one by one. After adding the $i$-th type A point, the plane contains $i$ type A points and all previously added type B points. Let the minimum total merge cost at this moment be $f(i)$.

Given a cost limit $L$, compute the maximum number $K$ of type A points such that the minimum total merge cost for the first $K$ type A points does not exceed $L$, i.e., $f(K) \le L$.

Input Format

The first line contains two numbers $M$, $L$, meaning there are $M$ add-point commands and the cost limit is $L$.

Then follow $M$ lines, each starting with a letter indicating the point type. A denotes a type A point, and B denotes a type B point. For a type A point, one number follows giving its $X$-coordinate; for a type B point, three numbers follow giving its $X$-coordinate, $Y$-coordinate, and weight.

Output Format

Output a single integer $K_{max}$, which is the largest $K$ such that $f(K) \le L$.

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

Hint

Sample explanation:

In the state after adding the last point, all points are as shown below. The number next to each type B point is its weight.

The minimum cost for the first $3$ type A points is $f(3) = 27$, and for the first $4$ type A points is $f(4) = 36$. Since $f(3) < 30$ and $f(4) > 30$, the maximum $K$ is $3$.

Constraints:

• $3 \le \text{number of type A points} \le 30000$.
• $5 \le M \le 100000$.
• $X$, $Y$ are integers with absolute value at most $10000000$.
• $L$, $W$ are real numbers with $0 < W \le 10000$, $L \le 10^{11}$; all input real numbers have at most three decimal places.
• $50\%$ of the testdata satisfies $M \le 3000$.

Translated by ChatGPT 5