Pairing Elements to Nullify Attack

Mami is facing an imminent attack from Charlotte, and only a precise pairing of two sets of energies—candy and pill—can nullify the attack. There are two groups: candy and pill, each containing n elements with a certain energy value. Before Charlotte's attack, each candy is paired with one pill, forming n pairs. For each pair, if the candy's energy is greater than the pill's energy, it contributes +1; if it is less, it contributes -1; and if they are equal, 0.

The overall condition to nullify Charlotte's attack is that the total difference, defined as the number of pairs where candy > pill minus the number of pairs where candy < pill, is exactly k. Formally, if we denote the pairing by a permutation \(\sigma\) (i.e. candy \(i\) is paired with pill \(\sigma(i)\)), we require:

$$\sum_{i=1}^{n} \delta(candy_i, pill_{\sigma(i)}) = k$$

where

$$\delta(a,b)=\begin{cases}1,&\text{if } a>b,\\ -1,&\text{if } a<b,\\ 0,&\text{if } a=b.\end{cases}$$

Your task is to compute the number of valid pairings (bijective mappings) from candies to pills that satisfy the above condition.

inputFormat

The input consists of three lines:

• The first line contains two integers n and k.
• The second line contains n integers, representing the energy values of the candies.
• The third line contains n integers, representing the energy values of the pills.

outputFormat

Output a single integer: the number of ways to pair the candies with the pills so that the difference (the number of pairs where candy > pill minus the number of pairs where candy < pill) equals k.

sample

2 0
1 2
2 1

2