Background

Description

OItown is holding its annual super dance party.

To make this year’s party bigger than ever, the organizer Constantine invited many of his friends and classmates.

On the day of the party, exactly $n$ boys and $n$ girls came.

Constantine noticed that, in general, in a pair the boy is taller than the girl, but there are occasional exceptions.

So Constantine wants to know: if we pair these $2n$ people into exactly $n$ couples, how many ways are there such that at most $k$ couples have the girl taller than the boy?

Now Constantine asks you, who is attending SHTSC, to compute the answer.

Of course, he will first tell you the heights of all $2n$ students.

Output Format

Output a single integer in one line: the number of pairing schemes where among the $n$ couples, at most $k$ couples have the girl taller than the boy.

3 0
178
188
176
168
178
170

4

Hint

Constraints: For $100\%$ of the testdata, $1 \le n \le 200$, $0 \le k \le n$, and all heights are positive integers not greater than $10^9$.

Translated by ChatGPT 5