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:
Card Game
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 605Accepted: 81

Description

Jack and Joe are playing a special card game in which each card has some points in three properties apo, bqu and cri. Jack has one card while Joe has the other N - 1 cards. Every round Joe picks one of his cards and compares it with Jack's card. The one has the more powerful card wins the round. The rule is as follows:

  • The card has more points in apo is more powerful.
  • If two cards have the same points in apo, the one has more points in bqu is more powerful.
  • If two cards have the same points in apo and bqu, one has more points in cri is more powerful.
  • If two cards have the same points in apo, bqu and cri, Jack's card is more powerful.

After the compare, Joe's card is discarded so that he can never use it any more.

To make the game more competitive, Jack and Joe are given m chances each to enhance the cards. For each time, Jack may add 1 point to either property of his card while Joe may add 1 point to bqu of one card and 1 point to cri of another.

Joe wants to know how many rounds he can win if they both plays optimally.

Input

Input consists several test case.

The first line of each test case is N (N ≤ 100000), the total number of cards.

The following N lines describe the cards. Each line contains three integers a, b, c (a, b, c ≤ 10000) which present the number of points in apo, bqu and cri of that card respectively. Jack has the first card.

The last of each test case is M (M ≤ 10000000), the number of chances to enhance cards.

The input ends with N = 0.

Output

For each test case, output how many rounds Joe can win.

Sample Input

3
0 0 0
1 0 0
1 0 0
1
3
0 0 0
0 0 0
0 0 0
0
0

Sample Output

2
0

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