Background

When going to the NOIP exam site, there are two fine traditions: “fighting wolves” and drinking “happy water”. Both activities can bring students happiness.

Problem Description

There are $n$ people in VG’s school who are going to take NOIP.

Each person has a way of transportation. For person $i$, the transportation is $t_i$. If $t_i=1$, this person takes the school bus; if $t_i=0$, this person goes to the exam site by themselves.

Each person has a “depressed value”. For person $i$, the depressed value is $q_i$. If $q_i=1$, this person is willing to “fight wolves”; if $q_i=0$, this person is not willing to “fight wolves”.

Everyone will buy one bottle of “happy water” when going to the exam site. However, if the number of people who both take the bus and are willing to “fight wolves” (i.e., the count of $i$ satisfying $t_i=1$ and $q_i=1$) is $k$, and $k$ is not less than $m$, then these $k$ people only need to buy $m$ bottles of “happy water” in total.

Now VG has collected everyone’s transportation and “depressed value”. Please help him compute the final total number of bottles of “happy water” bought by everyone.

Input Format

The first line contains three integers $n,m,type$. Here $type$ is the special constraint ID; see Constraints for its meaning. It may help you get partial scores, but the correct solution does not rely on it.

The second line contains $n$ integers, where the $i$-th integer is $t_i$.

The third line contains $n$ integers, where the $i$-th integer is $q_i$.

Output Format

Output one integer in one line, the final total number of bottles of “happy water” bought by everyone.

3 1 3
1 0 1
0 1 1

3

3 1 3
1 1 1
0 1 1

2

Hint

[Sample Explanation #1]

The situations of the three people are as follows:

• Person $1$ takes the bus but does not “fight wolves”;

• Person $2$ “fights wolves” but does not take the bus;

• Person $3$ takes the bus and also “fights wolves”.

So, only $1$ person both takes the bus and “fights wolves”, which satisfies the condition of being not less than $m$. Therefore, these $1$ person need to buy $m$ bottles of “happy water”, and the remaining $2$ people buy $2$ bottles of “happy water”. In total, $3$ bottles of “happy water” are needed.

[Constraints]

This problem does not use bundled testcases.

For $100\%$ of the data, $1 \le m \le n \le 100$, $t_i,q_i \in \{0,1\}$, $type \in \{0,1,2,3\}$.

Translated by ChatGPT 5