Description

Soon, the trees blossomed and bore fruit. byx and Shino-chan were surprised to find that theirs were Zhuzhu Trees, full of Zhuzhu and Zhuzhu’s friends. There are five kinds of people on the tree: Zhuzhu ($\verb!J!$), Jiji ($\verb!HK!$), Gaogao ($\verb!W!$), Wangwang ($\verb!E!$), and Waiwai ($\verb!YYY!$). They found that the numbers of people on their Zhuzhu Trees are the same, both equal to $N$.

Research shows that the win–lose relationships among the five kinds are as in the figure above (two people of the same kind cannot “PK”). Arrows point to the loser. As for why, think about it yourself.

The contest begins as scheduled.

byx and Shino-chan will play $M$ matches. In each match, they will each choose one person from their own tree to see who is stronger.

The $i$-th person has a lifetime of $\text{Life}_i$ seconds. After each match, both participants lose $-1\text{s}$. When someone’s lifetime reaches $0\text{s}$, they can no longer play.

Also, when a $\verb!J!$’s lifetime is $0$, any $\verb!YYY!$ on the same tree can add $+1\text{s}$ to that $\verb!J!$. Each $\verb!YYY!$ can extend each $\verb!J!$ at most once.

The problem:

Given $N, M (1\le N\le 100, 1\le M\le 1000)$, the kind of each person for Shino-chan and byx (one of $\verb!J!, \verb!HK!, \verb!W!, \verb!YYY!, \verb!E!$), and each person’s lifetime (not exceeding $50$), compute the maximum number of matches that byx can win.

The testdata guarantees that there will be available participants for every match. Any pair of two specific people can play at most one match.

Input Format

The first line contains two integers $N, M$, as described above.
The second line contains $N$ strings ($\verb!J!, \verb!HK!, \verb!W!, \verb!YYY!$ or $\verb!E!$), the kinds of byx’s people, separated by spaces.
The third line contains $N$ strings ($\verb!J!, \verb!HK!, \verb!W!, \verb!YYY!$ or $\verb!E!$), the kinds of Shino-chan’s people, separated by spaces.
The fourth line contains $N$ integers, the lifetimes of byx’s people.
The fifth line contains $N$ integers, the lifetimes of Shino-chan’s people.

Output Format

Output a single integer: the number of matches byx can win.

3 3
J W YYY
J HK E
2 2 2
2 2 2

3

Hint

In the first match, $\verb!J!$ beats $\verb!HK!$. In the second match, $\verb!W!$ beats $\verb!E!$. In the third match, $\verb!YYY!$ beats $\verb!HK!$.

Translated by ChatGPT 5