34410번 - 근성아 일 좀 하자

문제

근성은 나무에 관심이 많다.

평소 나무를 깨끗이 관리해 온 근성은 그 능력을 인정받아 북구청 청소행정과에 근무하게 되었다. 근성은 길거리에 버려진 쓰레기 더미를 수거하는 업무를 맡았는데, 어느 날 폭우로 인해 버려진 쓰레기 더미가 빗물을 떠다니게 되었다.

길은 1ドル$번 칸부터 $N$번 칸까지의 일직선 모양이며, 1ドル$번 칸의 왼쪽 경계와 $N$번 칸의 오른쪽 경계는 벽으로 막혀 있다.

처음에는 $M$개의 쓰레기 더미가 서로 한 칸 이상 떨어진 상태로 놓여있다. 각 쓰레기 더미는 위치와 무게, 이동 방향(오른쪽 또는 왼쪽)을 갖는다. 또한 쓰레기 더미는 정확히 한 칸의 길이를 차지한다.

움직이는 쓰레기 더미는 다른 쓰레기 더미 또는 벽에 충돌할 때까지 항상 이동 방향에 따라 1ドル$의 속도로 이동한다. 이때 충돌은 칸의 경계가 아닌 곳에서 일어날 수도 있다.

쓰레기 더미가 움직이며 발생하는 충돌에 대한 규칙은 다음과 같다.

• 벽은 질량이 무한하며, 움직이는 쓰레기 더미가 벽에 부딪히면 그 자리에서 즉시 정지한다. 벽에 붙어있는 쓰레기 더미와 충돌하는 때도 동일하다.
• 두 쓰레기 더미끼리 충돌하는 경우 하나의 쓰레기 더미로 합쳐진다.
  • 합쳐진 쓰레기 더미의 길이와 무게는 두 쓰레기 더미의 합이 된다.
  • 이동 방향은 더 무거운 쓰레기 더미의 이동 방향을 따른다. 단, 두 쓰레기 더미의 무게가 같은 경우 그 자리에서 정지한다.
• 정지한 쓰레기 더미에 충돌하는 상황 또한 두 쓰레기 더미가 충돌하는 규칙을 따른다. 단, 양쪽에서 동시에 정지한 쓰레기 더미에 충돌하는 경우 아래와 같이 합쳐진다.
  • 합쳐진 쓰레기 더미의 길이와 무게는 세 쓰레기 더미의 합이 된다.
  • 움직이는 두 쓰레기 더미의 무게가 같거나, 각 무게가 정지한 쓰레기 더미보다 가볍거나 같다면 그 자리에서 정지한다. 그렇지 않은 경우, 합쳐진 쓰레기 더미의 이동 방향은 더 무거운 쓰레기 더미의 이동 방향을 따른다.
• 합쳐진 쓰레기 더미는 하나의 쓰레기 더미로 이후 동일하게 규칙을 따른다.

근성은 시간이 지나면 모든 쓰레기 더미가 결국 정지하게 된다는 사실을 알게 되었다. 근성을 도와 모든 쓰레기 더미가 멈춘 시점과 그때의 쓰레기 더미의 수를 계산하자.

입력

첫 번째 줄에 길의 길이 $N$과 초기 쓰레기 더미의 개수 $M$이 공백으로 구분되어 주어진다.

두 번째 줄부터 $M$개의 줄에 걸쳐 각 쓰레기 더미의 위치 $x_i,ドル 무게 $w_i,ドル 이동 방향 $d_i$(L 또는 R)이 공백으로 구분되어 주어진다. L과 R은 각각 왼쪽, 오른쪽 이동을 나타낸다.

출력

첫 번째 줄에 모든 쓰레기 더미가 멈춘 시간과 그때의 쓰레기 더미의 수를 공백으로 구분하여 출력한다. 이때 시간은 소수점 첫째 자리까지 출력해야 하며, 항상 답을 정확하게 출력할 수 있음을 증명할 수 있다.

제한

• 1ドル \le M < N \le 100,000円$
• 1ドル \le x_i \le N$
• 1ドル \le w_i \le 10,000円$
• 입력으로 주어지는 모든 수는 정수이다.
• 각 쓰레기 더미의 시작 위치는 서로 한 칸 이상 떨어져 있다.

힌트