Bessie đã nhận công việc điều phối tàu! Có hai ga tàu là A và B. Do hạn chế về ngân sách, chỉ có một đường ray nối hai ga. Nếu một đoàn tàu khởi hành từ một ga vào thời điểm \(t\), thì nó sẽ đến ga còn lại vào thời điểm \(t+T\).

Có \(N\) đoàn tàu cần lên lịch khởi hành. Tàu thứ i phải rời ga si vào thời điểm ti hoặc muộn hơn \((s_i \in \{A, B\}\). Không được phép có hai tàu di chuyển ngược chiều cùng lúc trên đường ray (vì chúng sẽ đâm vào nhau). Tuy nhiên, có thể có nhiều tàu di chuyển cùng chiều trên đường ray cùng lúc (giả sử các tàu có kích thước nhỏ không đáng kể).

Hãy giúp Bessie lên lịch khởi hành cho tất cả các đoàn tàu sao cho không có va chạm và tổng độ trễ được giảm thiểu. Nếu tàu thứ \(i\) khởi hành vào thời điểm \(a_i \ge t_i\), tổng độ trễ được tính là \(\Sigma_{i = 1}^{N}(a_i − t_i)\).

Input

• Dòng đầu tiên chứa \(N\) và \(T\) \((1 \le N \le 5000; 1 \le T \le 10^{12})\).
• \(N\) dòng tiếp theo, mỗi dòng chứa ga \(s_i\) và thời gian \(t_i\) \((0 \le t_i \le 10^{12})\) của tàu thứ \(i\).

Output

• In ra tổng độ trễ tối thiểu có thể xảy ra.

Scoring

• Subtask 1: \(N \le 15\)
• Subtask 2: \(N \le 100\)
• Subtask 3: \(N \le 500\)
• Subtask 4: \(N \le 2000\)
• Subtask 5: Không có ràng buộc bổ sung.

Example

1 95
B 63

0

4 1
B 3
B 2
A 1
A 3

1

4 10
A 1
B 2
A 3
A 21

13

8 125000000000
B 17108575619
B 57117098303
A 42515717584
B 26473500855
A 108514697534
B 110763448122
B 117731666682
A 29117227954

548047356974