Meditation Disturber

Interview

Time limit2sMemory limit512 MB

Summary

Each bird on the left or right chirps on some seconds; remove one bird so the peak absolute value of the running signed sum over M seconds is minimized, and report its index and that value.

Level: Medium5 of 10
Topics: Prefix sum, Implementation, Brute force, Array
Solved: No attempts yet

Problem

Hyeonuk is helping his master, who is training in a mysterious jungle.

Today the master sits under a tree and meditates, with birds perched around him. Since the birds' chirping can disturb the master, Hyeonuk wants to help by catching one of the birds so that it cannot chirp.

There are N birds, and each is perched either to the master's left or to his right. The master is concentrating to keep his mind balanced. The center of his mind moves in the negative direction when a bird on the left chirps, and in the positive direction when a bird on the right chirps. A bird chirping for 1 second affects the center of the mind by 1. The master meditates for a total of M seconds, and the degree to which he is disturbed is the absolute value of the center of his mind at the moment it reaches its maximum absolute value during the meditation.

Through his training so far, Hyeonuk has become able to predict the birds' chirping. Find the bird Hyeonuk must catch so that the master is disturbed as little as possible. The center of the master's mind starts at 0, each bird's effect on the center of the mind is independent of the others, and the effects are applied simultaneously at the end of each second.

Input

The first line gives the integers N and M, separated by a space.

Each of the next N lines gives information about one bird. Each bird is assumed to be numbered with the integers 1 through N in the order it is given. First a single character, either L or R, is given, where L means that bird is on the master's left and R means it is on his right. Then, after one space, a string of length M consisting of 0 and 1 is given. The i-th character of the string indicates whether that bird chirps during the i-th second: 0 means it does not chirp, and 1 means it chirps.

Output

The first line prints the number of the bird Hyeonuk must catch. If there are several such birds, print the smallest number among them. He must catch exactly one bird.

The second line prints the degree to which the master is disturbed when that bird is caught.

Constraints

1 ≤ N,M ≤ 2000

Examples3

Example 1
Input
```
2 5
L 11000
R 11100
```
Expected output
```
2
2
```

Example 2

Input

Expected output

2
1

Example 3
Input
```
1 5
R 10101
```
Expected output
```
1
0
```