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 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.