Dance Partner Pairing with Height Constraint

OItown is hosting its annual Super Dance Party. As the organizer, Constantine invited many of his friends and classmates in order to make this year’s party unprecedentedly grand. On the day of the party, exactly n boys and n girls showed up. Typically, in a dance pair the boy is taller than the girl; however, there are occasional exceptions. Constantine now wonders: if the 2n people are paired into n dance couples, in how many different ways can they be paired so that at most k pairs have the girl taller than the boy?

You are also given the heights of the 2n participants. The first group of n numbers represents the heights of the boys and the next n numbers represents the heights of the girls.

More formally, suppose we have arrays B and G of length n representing the heights of boys and girls respectively. A pairing is a permutation P of {0, 1, ..., n-1} where boy i is paired with girl P(i). Let bad be the count of indices i where the pairing is "bad", i.e. where the height of the girl is greater than the height of the boy. We require that:

[ bad \le k ]

Output the total number of valid pairings.

Note: The intended solution uses dynamic programming with bitmasking. In the DP state dp[mask][bad], mask is a bitmask representing which girls have been paired so far and bad is the number of pairs where the girl is taller than the boy.

inputFormat

The first line contains two integers n and k (1 ≤ n ≤ 18, 0 ≤ k ≤ n).

The second line contains n space-separated integers representing the heights of the boys.

The third line contains n space-separated integers representing the heights of the girls.

outputFormat

Output a single integer—the total number of valid pairings in which at most k pairs have a girl taller than the paired boy.

sample

1 0
170
160

1