USACO 2023 - Tháng 1 - Hạng Đồng

Nông dân John có \(N\) con bò (\(2 \leq N \leq 10^5\)). Mỗi con bò thuộc một giống bò Guernsey hoặc Holstein. Như thường lệ, các con bò đứng thành một hàng, được đánh số từ \(1\) đến \(N\) theo thứ tự này.

Trong suốt cả ngày, mỗi con bò sẽ viết ra một danh sách các con bò. Cụ thể, danh sách của con bò thứ \(i\) chứa các con bò từ chính con bò đó (con bò \(i\)) đến con bò \(E_i\) (\(i \leq E_i \leq N\)).

John vừa phát hiện ra rằng mỗi giống bò có đúng một lãnh đạo riêng biệt. John không biết chính xác con nào là lãnh đạo, nhưng anh biết rằng mỗi lãnh đạo phải có một danh sách mà bao gồm tất cả các con bò cùng giống của nó hoặc lãnh đạo của giống bò khác (hoặc cả hai).

Hãy giúp John đếm số cặp có thể là lãnh đạo. Đảm bảo rằng luôn có ít nhất một cặp có thể là lãnh đạo.

Input

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ hai chứa một chuỗi có độ dài \(N\), với ký tự thứ \(i\) biểu thị giống của con bò thứ \(i\) (G có nghĩa là Guernsey và H có nghĩa là Holstein). Đảm bảo rằng luôn có ít nhất một con bò Guernsey và một con bò Holstein.
• Dòng thứ ba chứa các số nguyên \(E_1, \dots, E_N\).

Output

• In ra số lượng cặp có thể là người lãnh đạo.

Scoring

• Subtask 1: \(N \leq 100\).
• Subtask 2: \(N \leq 3000\).
• Subtask 3: Không có ràng buộc gì thêm.

Example

4
GHHG
2 4 3 4

1

3
GGH
2 3 3

2

Với mùa hè nóng nhất từng được ghi nhận tại nông trại của Nông dân John, ông cần một cách để làm mát cho các con bò của mình. Do đó, ông quyết định đầu tư vào một số máy điều hòa.

Có \(N\) con bò của Nông dân John (\(1 \leq N \leq 20\)) sống trong một dãy chuồng, được đánh số từ \(1\) đến \(100\). Con bò thứ \(i\) chiếm một phạm vi chuồng, bắt đầu từ chuồng \(s_i\) và kết thúc tại chuồng \(t_i\). Các phạm vi của các con bò khác nhau đều không chồng lấn lên nhau. Các con bò có yêu cầu làm mát khác nhau. Con bò thứ \(i\) cần được làm mát bởi số lượng \(c_i\), có nghĩa là mỗi chuồng mà con bò \(i\) chiếm phải giảm nhiệt độ ít nhất là \(c_i\) đơn vị.

Trong chuồng có \(M\) máy điều hòa, được đánh số từ \(1\) đến \(M\) (\(1 \leq M \leq 10\)). Máy điều hòa thứ \(i\) tốn \(m_i\) đơn vị tiền để hoạt động (\(1 \leq m_i \leq 1000\)) và làm mát phạm vi chuồng từ chuồng \(a_i\) đến chuồng \(b_i\). Nếu hoạt động, máy điều hòa thứ \(i\) giảm nhiệt độ của tất cả các chuồng trong phạm vi này đi \(p_i\) đơn vị (\(1 \leq p_i \leq 10^6\)). Các phạm vi chuồng của các máy điều hòa có thể chồng lấn lên nhau.

Hãy tính số tiền tối thiểu mà Nông dân John cần phải chi để vận hành đủ máy điều hòa để làm mát tất cả các con bò của mình. Đảm bảo rằng nếu Nông dân John sử dụng tất cả các máy điều hòa của mình, thì tất cả các con bò sẽ thoải mái.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\).
• \(N\) dòng tiếp theo mô tả thông tin về các con bò. Dòng thứ \(i\) chứa ba số nguyên \(s_i\), \(t_i\), và \(c_i\).
• \(M\) dòng tiếp theo mô tả thông tin về các máy điều hòa. Dòng thứ \(i\) chứa bốn số nguyên \(a_i\), \(b_i\), \(p_i\), và \(m_i\).
• Đối với các test khác test mẫu, bạn có thể giả định rằng \(M = 10\).

Output

• In ra một số nguyên duy nhất là số tiền tối thiểu mà Nông dân John cần phải chi để vận hành đủ máy điều hòa để làm mát tất cả các con bò.

Scoring

• Subtask 1: \(N \leq 5\).
• Subtask 2: \(N \leq 10\).
• Subtask 3: Không có ràng buộc gì thêm.

Example

2 4
1 5 2
7 9 3
2 9 2 3
1 6 2 8
1 2 4 2
6 9 1 5

10

Do Bessie chán chường với chuỗi văn bản thông thường chỉ có các ký tự 'C', 'O', và 'W', Nông dân John đã cho cô \(Q\) chuỗi mới (\(1 \leq Q \leq 100\)), trong đó các ký tự chỉ có thể là 'M' và 'O'. Từ yêu thích của Bessie với các ký tự 'M' và 'O' là "MOO", vì vậy cô muốn biến đổi từng chuỗi trong số \(Q\) chuỗi thành "MOO" bằng các thao tác sau:

1. Thay thế ký tự đầu tiên hoặc ký tự cuối cùng bằng ký tự ngược lại của nó (ví dụ 'M' thành 'O' và 'O' thành 'M').
2. Xóa ký tự đầu tiên hoặc ký tự cuối cùng.

Rất tiếc, Bessie rất lười biếng và không muốn thực hiện nhiều thao tác hơn là cần thiết. Vì vậy, với mỗi chuỗi, hãy giúp cô xác định số lượng thao tác tối thiểu cần thiết để biến đổi thành "MOO" hoặc xuất \(-1\) nếu điều này là không thể.

Input

• Dòng đầu tiên chứa giá trị \(Q\).
• \(Q\) dòng tiếp theo của đầu vào mỗi dòng gồm một chuỗi, mỗi ký tự trong đó là 'M' hoặc 'O'. Mỗi chuỗi có từ 1 đến 100 ký tự.

Output

• In ra kết quả cho mỗi chuỗi đầu vào trên một dòng riêng biệt.

Scoring

• Subtask 1: Mỗi chuỗi có độ dài tối đa là \(3\).
• Subtask 2: Không có ràng buộc gì thêm.

Example

3
MOMMOM
MMO
MOO

4
-1
0