15980번 - 명상 방해꾼 서브태스크

현욱은 신비로운 밀림 속에서 수행 중인 그의 스승님을 돕고 있다.

오늘은 스승님이 나무 밑에 앉아 명상을 하고 있고, 스승님 주변에는 새들이 앉아 있다. 새들이 지저귀면 스승님께 방해가 될 수 있기 때문에, 현욱은 그 중 한 마리를 잡아 지저귀지 못하게 하여 스승님의 명상을 도우려 한다.

새는 N마리가 있고, 각각 스승님의 왼편 또는 오른편에 앉아 있다. 스승님은 정신이 균형을 이루도록 집중하고 있는데, 정신의 중심은 왼편에 앉은 새가 지저귀면 음의 방향으로, 오른편에 앉은 새가 지저귀면 양의 방향으로 이동하게 된다. 각 새가 1초간 지저귀면 정신의 중심에 1만큼의 영향을 준다. 스승님은 총 M초간 명상하는데, 명상을 하는 중 정신의 중심의 절댓값이 최대가 된 순간, 그 절댓값이 스승님이 방해를 받은 정도가 된다.

현욱은 지금까지의 수련을 통해 새들의 지저귐을 예측할 수 있게 되었다. 현욱이 스승님이 방해를 가장 덜 받게 하기 위해 잡아야 할 새를 구해보자. 스승님의 정신의 중심은 처음에 0이고, 각 새가 스승님의 정신의 중심에 미치는 영향은 모두 독립적이며, 그 영향은 매 초가 끝날 때마다 동시에 적용된다.

첫째 줄에 정수 N과 M이 공백을 사이에 두고 주어진다.

둘째 줄부터 N개의 줄에 걸쳐 각 새에 대한 정보가 주어진다. 각 새에는 입력되는 순서대로 1부터 N까지의 정수 번호가 차례로 붙어 있다고 가정한다. 우선 L과 R중 하나의 문자가 주어지는데, L은 그 새가 스승님의 왼쪽에 있다는 뜻이고, R은 오른쪽에 있다는 뜻이다. 그 후 공백이 하나 주어진 뒤, 0과 1로 이루어진 길이 M의 문자열이 주어진다. 문자열의 i번째 문자는 i번째 초에 그 새가 지저귀는가에 대한 여부이고, 이 문자가 0이면 지저귀지 않는 것, 1이면 지저귀는 것이다.

첫째 줄에는 현욱이 잡아야 할 새의 번호를 출력한다. 만일 잡을 수 있는 새가 여럿이라면 그 중 가장 작은 번호를 출력한다. 새는 반드시 한 마리 잡아야 한다.

둘째 줄에는 그 새를 잡았을 때 스승님이 방해받는 정도를 출력한다.

• 1 ≤ N,M ≤ 2000

•  1 ≤ N, M ≤ 500

• 추가 제한 없음