Câu 4 (4.0 điểm). Thẻ bài

Sau khi hoàn thành 2 trò chơi thú vị của lễ hội, An cảm thấy rất hứng thú và cậu quyết định chơi trò chơi cuối cùng. An chọn trò chơi có thưởng của lễ hội do một ông giáo về hưu trong làng chủ trì.

Ông giáo xếp các ống tre màu xanh hoặc đỏ thành một hoặc hai hàng ngang. Ông giáo có \(10^6\) thẻ bài được xếp thành một chồng, được đánh số từ \(1\) đến \(10^6\) theo thứ tự từ trên xuống dưới. Bắt đầu trò chơi, An bốc lần lượt các thẻ bài từ trên xuống dưới của chồng bài này và không bỏ thẻ bài nào vào bất kì ống tre nào (kể cả trong những lượt bốc sau) hoặc bỏ thẻ bài đó vào một ống tre thỏa mãn các yêu cầu:

• Mỗi ống tre chứa đúng một thẻ bài duy nhất.
• Thẻ số chẵn chỉ được bỏ vào ống màu xanh, thẻ số lẻ chỉ được bỏ vào ống màu đỏ.
• Chỉ được bỏ thẻ bài vào ống tre thứ \(i\) khi các ống tre \(1,2,\ldots,i-1\) của hàng đó đã được bỏ thẻ bài.

Trò chơi kết thúc khi An đã bỏ thẻ bài vào tất cả các ống tre mà ông giáo xếp ra. Điểm thưởng của An đạt được là số thẻ bài còn lại trong chồng bài ban đầu.

Yêu cầu
Hãy tìm số điểm mà An đạt được.

Input

Nhập từ tệp B4.INP:

• Dòng 1: Ghi số \(k\) bằng \(1\) hoặc \(2\) thể hiện số lượng hàng ngang ông giáo xếp ra.
• Dòng 2: Ghi một chuỗi có độ dài không quá \(5000\) kí tự, gồm hai loại kí tự B và R mô tả hàng ống tre thứ nhất.
• Dòng 3 (nếu có): Ghi một chuỗi có độ dài không quá \(5000\) kí tự mô tả hàng ống tre thứ hai.

Output

Ghi ra tệp B4.OUT gồm 1 dòng chứa số điểm cao nhất có thể đạt được.

Example

1
BRR

999995

2
BRR
BBB

999992

2
BRBRB
RBRB

999990

Scoring

• \(20\%\) số test thỏa mãn \(k = 1\).
• \(30\%\) số test thỏa mãn \(k = 2\) và hai hàng giống nhau.
• \(50\%\) số test thỏa mãn \(k = 2\) và không ràng buộc gì thêm.