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 trước khi về. 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 gồm hai 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 và chọn không bỏ thẻ bài này 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, \dots, 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.

Với sự thông minh của mình thì trò chơi của ông giáo đã không làm khó được An và cậu đã đạt được số điểm cao nhất của trò chơi.

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

Dữ liệu: Nhập từ tệp B4.INP có cấu trúc:

• 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 (B tương ứng với ống tre màu xanh và R tương ứng với ống tre màu đỏ) mô tả hàng ống tre thứ nhất.
• Dòng 3: tùy vào giá trị của $k$, cụ thể:
  • $k = 1$: bỏ trống
  • $k = 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 (B tương ứng với ống tre màu xanh và R tương ứng với ống tre màu đỏ) mô tả hàng ống tre thứ hai.

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

• 20% số test tương ứng 20% số điểm thoả mãn $k = 1$;
• 30% số test tương ứng 30% số điểm thoả mãn $k = 2$ và dòng 2 có các kí tự giống nhau;
• 50% số test tương ứng 50% số điểm thoả mãn $k = 2$ và không ràng buộc gì thêm.