502013 - 补给

【题目描述】补给

探险队在准备探险的补给方案，即给定n和k，已知n个葡萄糖能量ai和n个维生素药片能量bi，每个ai和bi互不相等。将葡萄糖和维生素药片一一对应，求恰好葡萄糖比维生素药片能量大的组数比“药片”比“葡萄糖”能量大的组数多k 组的方案数。

第一行两个整数n和k（1≤n≤2000，0≤k≤n）。 接下来一行n个整数，第i个数表示第i个葡萄糖的能量。 接下来n个整数，第j个数表示第j个维生素药片的能量。 保证上面两行不会有重复的数字。

一个答案，表示方案数，需要对10^9+9取模。

方案为：(5-40,35-20,15-10,45-30)，(5-40,45-20,15-10,35-30)，(45-40,5-20,15-10,35-30)，(45-40,35-20,15-10,5-30)。