input:show.in output:show.out

Time Limits: 1000 ms Memory Limits: 262144 KB

Description

有三支队伍,分别是A,B,C。有n个游戏节目,玩第i个游戏,队伍A可以得到的分数是A[i],队伍B可以得到的分数是B[i],队伍C可以得到的分数是C[i]。由于时间有限,可能不是每个节目都能玩,于是节目主持人决定要从n个游戏节目里面挑选至少k个节目出来(被选中的节目不分次序),使得队伍A成为赢家。队伍A能成为赢家的条件是队伍A的总得分要比队伍B的总得分要高,同时也要比队伍C的总得分要高。节目主持人有多少种不同的选取方案?

Input

第一行,两个整数n和k。

第二行, n个整数,分别是A[1]、A[2]、A[3]…A[n]。

第三行, n个整数,分别是B[1]、B[2]、B[3]…B[n]。

第四行, n个整数,分别是C[1]、C[2]、C[3]…C[n]。

Output

一个整数,表示不同的选取方案数量。

Sample Input

1
2
3
4
3 2
1 1 2
1 1 1
1 1 1

Sample Output

1
2
3
4
5
3
【样例解释】
方案一:选取节目1和节目3。
方案二:选取节目2和节目3。
方案三:选取节目1、节目2、节目3。

Data Constraint

对于40%数据,2 <= n <= 20。

对于100%数据,2 <= n <= 34, 1 <= k <= min(n,7), 1 <=A[i], B[i], C[i]<= 10^9。