Thế kỷ 21 là thế kỷ của khoa học sự sống. Con người đầu tư nhiều nhân lực và vật lực vào nghiên cứu lĩnh vực này nhằm hiểu sâu hơn cơ chế sinh tồn của các loài, qua đó hiểu rõ chính mình và nâng cao chất lượng sống. Chính phủ nước Q bắt đầu nghiên cứu thay đổi giới tính ở cừu, hy vọng tăng khả năng sinh tồn của cả quần thể bằng cách thay đổi giới tính qua tái tổ hợp gen. Nếu nghiên cứu thành công, con người sẽ nắm được công nghệ kỳ diệu có thể tùy ý thay đổi giới tính động vật, một cột mốc quan trọng trong lịch sử khoa học sự sống.

Chính phủ nước Q chọn $M$ con cừu làm mẫu thí nghiệm. Trong số đó có $K$ chuỗi huyết thống đơn giới tính, mỗi chuỗi dài $N$. “Chuỗi huyết thống” là chuỗi các quan hệ cha (mẹ) – con trai (con gái), chẳng hạn ông – cha – con trai. “Đơn giới tính” nghĩa là mọi cá thể trong một chuỗi đều cùng giới, hoặc đều đực hoặc đều cái. Độ dài chuỗi là số cá thể trong chuỗi; ví dụ ông – cha – con trai là chuỗi dài 3. $K$ chuỗi này không giao nhau.

Không phải con cừu nào cũng nhất thiết thuộc một chuỗi; một số có thể không thuộc chuỗi nào, nên $NK\le M$. Ngoài các chuỗi huyết thống, những con cừu cùng thế hệ còn có thể có “quan hệ sinh sản”. Hai con khác giới đã từng sinh con với nhau sẽ có quan hệ này. Quan hệ sinh sản chỉ xuất hiện giữa các cá thể khác giới cùng thế hệ. “Cùng thế hệ” nghĩa là cùng vai vế: một con cừu chỉ có quan hệ sinh sản với những con thuộc thế hệ anh chị em của nó, không phải thế hệ cha mẹ, con cái hay các thế hệ xa hơn.

Thay đổi giới tính cừu tốn chi phí thí nghiệm rất lớn. Chi phí thay đổi giới tính con $i$ là $c_i$. Việc thay đổi cũng ảnh hưởng đến độ ổn định của quan hệ sinh sản: quan hệ $j$ có độ ổn định ban đầu $b_j$ và hệ số suy giảm $d_j$. Sau khi hoàn thành mọi thay đổi, nếu cả hai bên không đổi giới tính thì $s_j=b_j$; nếu cả hai bên đổi giới tính thì $s_j=\lfloor b_jd_j\rfloor$; các trường hợp khác có $s_j=0$.

Cho giới tính, chi phí thay đổi của từng con cừu cùng mọi chuỗi huyết thống và quan hệ sinh sản, chính phủ nước Q muốn bạn thiết kế phương án thay đổi giới tính có lợi nhuận lớn nhất. Lợi nhuận được tính như sau:

$$Profit=\lfloor10\ln(1+A)\rfloor\cdot S-C$$

Ở đây $A$ là số cặp kề nhau trên các chuỗi huyết thống có giới tính khác nhau sau thay đổi; $S$ là tổng độ ổn định của các quan hệ sinh sản sau thay đổi, tức $S=\sum_j s_j$; $C$ là tổng chi phí thay đổi giới tính cừu, tức $C=\sum_i c_i$.

Dữ liệu vào

Tệp dữ liệu vào là gender.in.

Dòng đầu có bốn số nguyên không âm $N,K,M,P$, lần lượt là độ dài chuỗi huyết thống, số chuỗi, tổng số cừu trong mẫu thí nghiệm và số quan hệ sinh sản.

Dòng thứ hai là một xâu gồm $M$ ký tự, mỗi ký tự là M hoặc F, mô tả giới tính ban đầu của $M$ con cừu. M chỉ đực, F chỉ cái.

Dòng thứ ba có $M$ số nguyên dương $c_i$, là chi phí thay đổi giới tính từng con cừu.

$K$ dòng tiếp theo, mỗi dòng có $N$ số nguyên mô tả số hiệu các con cừu trong một chuỗi huyết thống (cừu được đánh số từ $1$ đến $M$). Đảm bảo mọi con trong mỗi chuỗi cùng giới và các chuỗi không giao nhau.

$P$ dòng tiếp theo, mỗi dòng có ba số nguyên dương $x,y,b$ và một số thực $d$, nghĩa là cừu $x$ và $y$ có quan hệ sinh sản với độ ổn định ban đầu $b$ và hệ số suy giảm $d$. Đảm bảo $x$ và $y$ ban đầu khác giới và cùng thế hệ. Mỗi quan hệ chỉ được mô tả một lần.

Dữ liệu ra

Tệp gender.out chỉ chứa một dòng với một số nguyên, là lợi nhuận lớn nhất của phương án thay đổi.

Ví dụ

Dữ liệu vào 1

3 2 6 2
MMMFFF
10000 200 10 10000 200 10
1 2 3
4 5 6
2 5 20 0.1
3 6 20 0.9

Dữ liệu ra 1

360

Ghi chú

Đổi giới tính thành MMFFFM. Lợi nhuận là $\lfloor10\ln(1+2)\rfloor\times(20+18)-(10+10)=360$.

$A=2$ vì trên chuỗi $1-2-3$, cừu $2$ và $3$ khác giới; trên chuỗi $4-5-6$, cừu $5$ và $6$ khác giới.

Dữ liệu vào 2

3 2 7 3
MMMFFFM
10 200 10 10 200 10 10
1 2 3
4 5 6
2 5 20 0.1
3 6 20 0.9
5 7 20 0.5

Dữ liệu ra 2

888

Ghi chú

Đổi giới tính thành FMFMFMM. Lợi nhuận là $\lfloor10\ln(1+4)\rfloor\times(20+18+20)-(10+10+10+10)=888$.

$A=4$ vì trên chuỗi $1-2-3$, cừu $1$ và $2$ khác giới, $2$ và $3$ khác giới; trên chuỗi $4-5-6$, cừu $4$ và $5$ khác giới, $5$ và $6$ khác giới; tổng cộng có 4 cặp khác giới.

Ví dụ 3

Xem các tệp gender/gender.in và gender/gender.ans trong thư mục thí sinh.

Giới hạn

Với $10\%$ dữ liệu, $M\le20$;

Với $10\%$ dữ liệu, $d_j=0$;

Với $10\%$ dữ liệu, $d_j=0.5$;

Ba nhóm dữ liệu trên đôi một không giao nhau.

Với $100\%$ dữ liệu, $N\le50$, $K\le4$, $M\le1000$, $P\le10000$, $0.0\le d_j\le1.0$; $b_j$ và $c_i$ đều không vượt quá $10000$; $d_j$ có không quá 6 chữ số sau dấu thập phân.