Farmer John đã nghĩ ra một phương pháp tuyệt vời để sơn hàng rào dài cạnh chuồng của mình (hãy xem hàng rào như một trục số một chiều). Ông chỉ việc gắn một chiếc chổi sơn vào Bessie, con bò yêu thích của mình, rồi thong thả đi uống một ly nước lạnh trong khi Bessie đi tới đi lui dọc hàng rào và quét sơn lên mọi đoạn hàng rào mà cô đi qua.

Bessie bắt đầu tại vị trí \(0\) trên hàng rào và thực hiện một chuỗi \(N\) bước di chuyển (\(1 \le N \le 100\,000\)). Chẳng hạn, bước 10 L nghĩa là Bessie di chuyển \(10\) đơn vị sang trái, còn 15 R nghĩa là Bessie di chuyển \(15\) đơn vị sang phải. Với danh sách tất cả các bước di chuyển của Bessie, FJ muốn biết phần nào của hàng rào được phủ ít nhất \(K\) lớp sơn. Trong suốt hành trình, Bessie sẽ cách gốc tọa độ không quá \(1\,000\,000\,000\) đơn vị.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\), cách nhau bởi dấu cách.
• \(N\) dòng tiếp theo, mỗi dòng mô tả một bước di chuyển của Bessie (chẳng hạn 15 L).

Dữ liệu ra

In ra tổng độ dài được phủ ít nhất \(K\) lớp sơn.

Ví dụ

6 2
2 R
6 L
1 R
8 L
1 R
2 R

6

Nguồn

USACO 2013 January Contest, Silver — Problem 1: Painting the Fence

Tác giả đề: Brian Dean, 2012.