Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
System Test
Time Limit: 10000MSMemory Limit: 65536K
Total Submissions: 193Accepted: 59
Case Time Limit: 3000MS

Description

A semi-final competition was just over. There are n players. Each player had an SEED number from 1 to n. The competition had m problems in coding phase and challenge phase. The final rank was decided by the total score of the m problems and challenge scores. The higher the total score was, the higher a player ranked. If two players got the same total score, the one with the smaller SEED number got a higher rank. We know that for each problem, how much score each player might get if his solution is correct (if not, the player got 0 in the problem). And we also know how much score each player get during the challenge phase.

After the system-tests, the c1 highest ranked players will advance to the final round, the next c2 highest scoring players will advanced to wildcard round.

Before the system-tests, you need to count how many different combinations of advancers (including finalist and wildcard participants) are possible. Two ranks with same set of finalist and wildcard participants are consider same here. Note that, the players with negative scores can also advance to the final round or wildcard round, because the challenge scores may be smaller than 0.

Input

The first line of input four integers n, m, c1, c2, denote the number of players, the number of problems, the number of finalist and the number of player will advanced to wildcard round. 3 ≤ n ≤ 40, 1 ≤ m ≤ 40, c1 ≥ 1, c2 ≥ 1, n-c1-c2 ≥ 1
Following n lines, the i-th line contains m+2 integers Si, Ai1, Ai2, ……Aim, Ci denote the SEED number, the scores of the m problems and the score during the challenge phase for player i. All Si will be distinct. 1 ≤ Sin, 0 ≤ Aij ≤ 1000, -2000 ≤ Ci ≤ 2000

Output

The first line of output contains one integer denoting the number of different advancers.  

Sample Input

Sample Input 1
3 1 1 1
1 10 0
2 10 0
3 10 0
Sample Input 2
6 1 2 2
1 10 0
2 10 0
3 10 0
4 10 0
5 10 0
6 10 0

Sample Output

Sample Output 1
5
Sample Output 2
43

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator