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。