Description

你现在希望组建一支足球队，一支足球队一般来说由11人组成。这11人有四种不同的职业：守门员、后卫、中锋、前锋组成。你在组队的时候必须满足以下规则：

1. 足球队恰好由11人组成。
2. 11人中恰好有一名守门员，3-5 名后卫，2-5 名中锋，1-3 名前锋。
3. 你需要从这11人中选出一名队长。
4. 你这个足球队的价值是11人的价值之和再加上队长的价值，也就是说 队长的价值会被计算两次。
5. 你这个足球队的花费是11人的花费之和，你的花费之和不能超过给定的上限。

现在告诉你球员的总数，每个球员的职业、价值、花费，以及花费的上限，你希望在满足要求的情况下，达到以下目标：

1. 最大化队伍的价值。
2. 在最大化队伍的价值的情况下，最小化队伍的花费。
3. 在满足以上两个要求的情况下，有多少种选择球员的方案。如果有两种方案它们的区别仅仅是队长不一样，那么这两种方案应该被认为是一种方案。

你的任务是输出这三个值：价值、花费、方案数。

Format

Input

第一行一个正整数\(N\)，代表可选的球员个数。
接下来\(N\)行，每行描述一个球员的信息。每行开始是一个字符串，可能的字符串有 Goalkeeper、Defender、Midfielder、Forward，分别代表该球员的职业是守门员、后卫、中锋、前锋。接下来两个数\(V,C\)，分别代表该球员的价值和花费。
最后一行一个整数，代表花费的上限。
数据保证一定存在一种解。

Output

一行三个整数，分表代表最大价值、最小花费和方案数。如果方案数超过了\(10^9\)，则直接输出\(10^9\)。

Sample 1

Input

15
Defender 23 45
Midfielder 178 85
Goalkeeper 57 50
Goalkeeper 57 50
Defender 0 45
Forward 6 60
Midfielder 20 50
Goalkeeper 0 50
Midfielder 64 65
Midfielder 109 70
Forward 211 100
Defender 0 40
Defender 29 45
Midfielder 57 60
Defender 52 45
600

Output

716 600 2

Limitation

1s, 512MiB for each test case.

Hint

样例解释

选择所有的五名后卫，选择价值为\(178,20,64,109\)的中锋和价值为\(6\)的前锋，
两名守门员任意选择。选择价值为\(178\)的中锋作为队长。

数据规模与约定

对于30%的数据，\(N ≤ 20\)。
对于60%的数据，费用上限足够大。
对于100%的数据，\(1 ≤ N ≤ 500\)，所有球员的价值和花费以及花费上限均在\([0,1000]\)。

Source

csp2019模拟题七