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

There are two types of points, referred to as type A and type B (as shown in Figure 1, where black squares represent type A points and small black dots represent type B points). Type A points are always located on the X-axis and do not overlap, while type B points can appear anywhere on the plane and may overlap. Each type B point has a weight $W$.

Figure 1. Type A points and type B points. Figure 2. Initial squares.

Processing: 1. Initially, connect a square tilted at 45 degrees to the X-axis between every two adjacent type A points (as shown in Figure 2). 2. Each operation allows merging any two squares that share a common point into one larger square; after the merge, the two smaller squares disappear. The second and third squares from the left in Figure 2 are shown as a gray-bordered square in Figure 3 after being merged.

Figure 3. Merge result and cost calculation diagram.

The merged square divides the plane into 9 regions. The 4 regions adjacent to the 4 sides of the square are labeled I, II, III, and IV in Figure 3. Let $w_1$ be the sum of weights of type B points falling into region I, $w_2$ be the sum of weights of type B points in region II, $w_3$ be the sum of weights of type B points in region III, and $w_4$ be the sum of weights of type B points in region IV. Let $w_5$ be the sum of weights of type B points falling inside the gray square (it is guaranteed that type B points will not appear on the boundary of any region). The merge cost is $1w_1 + 2w_2 + 3w_3 + 4w_4 + 5w_5$. Type B points falling into other regions are not considered. Each merge does not affect the position of type B points on the plane or their own weights.

Each merge reduces the number of squares formed by type A points by one, until only one square remains. The total merge cost is the sum of the costs of each individual merge. 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, there are $i$ type A points on the plane along with all previously added type B points. Let the minimum merge cost at this time be $f(i)$.

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

Input

The first line contains two numbers $M$ and $L$, representing $M$ commands to add points and the cost limit $L$. The following $M$ lines each contain a letter indicating the type of point. "A" denotes a type A point, and "B" denotes a type B point. For type A points, the following number represents the X-coordinate of the point; for type B points, the following three numbers represent the X-coordinate, Y-coordinate, and the weight of the point.

Output

The output file contains only one integer $K_{max}$, the maximum $K$ such that $f(K) \le L$.

Examples

Input 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

Output 1

3

Note 1

When the last point is input, all points are as shown in the figure below. The numbers next to the type B points are their weights.

The minimum cost to merge the first 3 points is $f(3) = 27$, and the minimum cost to merge the first 4 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 values not exceeding $10000000$
• $L, W$ are real numbers, $0 < W \le 10000$, $L \le 10^{11}$, all input real numbers have at most three decimal places
• $50\%$ of the data satisfies $M \le 3000$