Optimal Merging Under Cost Constraint

You are given a sequence of commands adding points to an initially empty 2D plane. There are two types of points:

• A‐points: They lie on the x‑axis and no two A‑points share the same x‑coordinate.
• B‑points: They can be anywhere on the plane and may overlap. Each B‑point has an associated weight W (an integer).

After points are added, whenever an A‑point is added, the current configuration consists of the A‑points added so far (in their original order) and all B‑points that were added before that A‑point.

For any configuration with at least two A‑points, the initial structure is formed by drawing rotated squares between every pair of consecutive A‑points. Specifically, if two consecutive A‑points are located at (L, 0) and (R, 0) (with L < R), an initial square is constructed as a diamond (i.e. a square rotated by 45°) with vertices at (L,0), ((L+R)/2, (R-L)/2), (R,0) and ((L+R)/2, -(R-L)/2).

The squares are then merged step‐by‐step. In each merge operation you may choose any two squares that share at least one common point and merge them into a new square that exactly covers the extreme A‑points of the merged set. (After merging the squares corresponding to A‑points at (a_i,0) and (a_j,0) with a_i < a_j, the resulting square is the diamond with vertices (a_i,0), ((a_i+a_j)/2, (a_j-a_i)/2), (a_j,0) and ((a_i+a_j)/2, -(a_j-a_i)/2).)

Each merged square partitions the plane into 9 regions. Five of these regions will contribute to the merge cost as follows. Define mid = (L+R)/2 and r = (R-L)/2 for a merged square defined by extreme A‑points at x‑coordinates L and R. For any B‑point (x, y) with weight w (which is not located on any boundary), let its contribution be determined as follows:

1. If |x - mid| + |y| < r (i.e. the B‑point lies strictly inside the diamond), its weight contributes with a multiplier of 5.
2. Else if y > 0 and |x - mid| < y, it lies in region I (adjacent to the top edge) and contributes 1 * w.
3. Else if x > mid and |y| < x - mid, it lies in region II (adjacent to the right edge) and contributes 2 * w.
4. Else if y < 0 and |x - mid| < -y, it lies in region III (adjacent to the bottom edge) and contributes 3 * w.
5. Else if x < mid and |y| < mid - x, it lies in region IV (adjacent to the left edge) and contributes 4 * w.
6. Otherwise, the point does not contribute anything.

The cost of a merge operation is the sum of the contributions of all B‑points currently present (they remain fixed throughout merges). Since there will be exactly number_of_squares - 1 merge operations to combine all the squares into one, different merge orders may yield different total merge costs. Define f(i) as the minimum possible total merge cost achievable when there are i A‑points (and all B‑points added before the i‑th A‑point have been considered).

You are given a cost limit L. Determine the maximum number K of A‑points (taken in the order of addition) such that f(K) ≤ L. Note that when there is only one A‑point, no merge operation occurs so f(1) = 0.

---

Input Format

The first line contains two integers N and L (1 ≤ N ≤ 100, 0 ≤ L ≤ 10⁹), where N is the total number of point‐addition commands.

The following N lines each describe a command. A command is in one of the following two formats:

• A x: Add an A‑point at x‑coordinate x (an integer; |x| ≤ 10⁹). It is guaranteed that no two A‑points have the same x‑coordinate.
• B x y w: Add a B‑point at coordinates (x, y) with weight w (all integers; |x|, |y| ≤ 10⁹, 1 ≤ w ≤ 10⁵).

Output Format

Output a single integer: the maximum number K of A‑points (from the beginning of the command sequence) such that the minimum total merge cost f(K) does not exceed L.

---

Note: It is guaranteed that for each configuration the B‑points will never lie exactly on any boundary involved in the cost calculation.

inputFormat

First line: two integers N and L.

Next N lines: each line is either in the format A x or B x y w as described above.

outputFormat

A single integer representing the maximum number of A‑points (in order) for which the minimum merge cost is at most L.

sample

5 10
A 0
B 5 6 2
A 10
B 7 7 3
A 20

3