<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

400. The last hour of the contest
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



It's your lucky day - your team took part in the world finals programming contest. The competition has just finished and all competitors are looking forward to the results. Of course your team is not an exception.

According to the rules of the competition, duration of the contest is 5 hours and team standings are frozen during the last hour of the contest — from 241st to 300th minute. Due to this reason the actual results are unknown to the participants and are only announced at the awards ceremony. It is a long-term tradition though, to get a balloon at the world finals for every problem solved. This information can sometimes be of use during the competition.

While waiting for the awards ceremony, your team decided to evaluate chances to win and determine the place which it can take in the final standings. Here is the information that you have:



Standings table at the end of the 240th minute

Total amount of balloons given to all teams within the last hour

Exact rules of the competition



To solve this problem you should mind the following contest rules:



The competition lasts for 300 minutes, minutes are numbered from 1 to the 300.

Position of a team is defined by the amount of the problems solved and penalty time.

The more problems are solved the higher place a team gets. If two or more teams have the same amount of problems solved, the sorting is done by the penalty time in ascending order (less penalty time — higher place). If two or more teams have the same amount of problems solved and the same penalty time, they share the same place. Rank of a team equals the number of teams performing better + 1. If there are no other teams performing better, the team takes the 1st place.

Total penalty time is the sum of the penalty times consumed for each problem solved. The time consumed for a solved problem is the number of a minute (i. e. an integer between 1 and 300) when the correct submission was made plus 20 penalty minutes for every previously rejected run for that problem. There is no penalty time for a problem that is not solved.

When solution for a particular problem is accepted, a team is not allowed to submit solutions of the same problem anymore.



Frozen standings are given to you in a text form and look as follows:



The first line consists of "", "", "", and "" tokens followed by a list of problems identifiers. Every problem identifier is a capital Latin letter 'A'-'Z'. All problem identifiers are different.

The second and the subsequent lines contain team standings itself. These lines are given to you. in non-descending order of team rank

Every line contains a place of a team, a name of a team, the amount of problems solved and the result for every problem.

Every result on a problem is



character "", if the team didn't submit the problem;
"", if the problem was not accepted and the team made x unsuccessful submits;

"", if the problem was accepted and the team made x unsuccessful submits before the accepted run; x is always omitted if it equals to 0.





You are given the frozen standings, and your task is to calculate the minimum and the maximum place your team can get after the contest is over.

Input
Input file contains one or more set of input data.

First lines of each set contain the standings table at the end of the 240th minute in the format described above. In each line the tokens are split with at least one whitespace character. The next line contains the amount of balloons given to all teams within the last hour of the contest (from 241st to 300th minutes). The last line of the set is the name of your team. All team names consist of Latin letters 'A'-'Z', 'a'-'z', numbers and whitespaces. Each team name contains no more than 100 characters, doesn't start/end with a whitespace, and contains not less then 1 non-whitespace character. All team names are unique within a single set of input data. The number of teams is between 1 and 100. The number of problems is between 1 and 26. The total number of rejected attempts in frozen standings table is not more than 1000, but the total number of rejected attempts in final standings is unlimited. The number of balloons is non-negative.

You may assume that the size of the input file is not more than 100 KB.

Output
For every input data set, please print two integer numbers in the line — the minimum and the maximum place your team can get after the contest is over.

Example(s)
sample input
sample output
Rank Team = Penalty X Y
1 Tarasov SU 3 2 33 + +
2 IMHO 1 1 20 + -1
3 Mozgow SU x 33 1 30. +
3 MiTV 1 30 + -3
5 Opel SU 0 0..
2
MiTV
Rank Team = Penalty A
1 aa 0 0 -1
1 ba 0 0 -8
2
ba

<|response|>
## 1. Abridged problem statement

A programming contest lasts 300 minutes. The standings are frozen after minute 240, but teams may still solve problems during minutes 241–300. Each accepted problem in the last hour gives one balloon.

You are given:

- the frozen standings table,
- the total number of balloons given in the last hour,
- your team name.

Using ICPC ranking rules — more solved problems is better, then smaller penalty is better, equal solved and penalty means shared rank — determine:

```text
minimum possible final place of your team
maximum possible final place of your team
```

There may be multiple test cases until EOF.

---

## 2. Key observations

### Last-hour accepted submissions

If a team solves an unsolved problem during the last hour, the earliest possible accepted time is minute `241`.

If that problem already had `x` wrong submissions before the freeze, the minimum additional penalty is:

```text
241 + 20 * x
```

Extra wrong submissions during the last hour can only increase penalty.

---

### We only need unsolved problems

For every team, frozen solved problems are fixed forever.

For every unsolved problem, we only care about the number of previous wrong submissions, because if the team solves it after the freeze, this affects the additional penalty.

So for each team we store:

```text
name
frozen solved count
frozen penalty
frozen rank
list of reject counts for unsolved problems
```

---

### Parsing is tricky

Team names may contain spaces and digits.

Example:

```text
1 Tarasov SU 3 2 33 + +
```

The team name is not easily parsed from the left.

However, the right side is structured:

```text
problem results, penalty, solved count
```

So each team row should be parsed from right to left.

---

### Best possible place

To get the best rank for our team:

1. Give as many last-hour accepted problems as possible to our team.
2. Always solve the currently cheapest unsolved problem, i.e. the one with the smallest previous reject count.
3. Then compare our improved team with teams originally above us.

---

### Worst possible place

To get the worst rank:

1. Keep our team unchanged.
2. Use balloons to make as many teams below us as possible overtake us.
3. A lower team can overtake us in two ways:
   - solve enough problems to have the same solved count and smaller penalty;
   - solve one more problem than us.

Teams are processed in groups with the same frozen solved count.

---

## 3. Full solution approach

### Helper comparison

Team `a` is strictly better than team `b` if:

```text
a.solved > b.solved
```

or

```text
a.solved == b.solved and a.penalty < b.penalty
```

Equal solved and equal penalty means neither team is better.

---

### Simulating one accepted problem

For a team, to minimize its penalty after one accepted problem, choose an unsolved problem with the smallest previous reject count.

If that reject count is `r`, then:

```text
team.solved += 1
team.penalty += 241 + 20 * r
```

Then remove that problem from the unsolved list.

---

### Computing the minimum possible place

Let our team be `me`.

While there are balloons and our team still has unsolved problems:

```text
accept the cheapest unsolved problem for me
balloons -= 1
```

After this, our state is as good as possible.

Remaining balloons can usually be assigned to other teams in a harmless way, because extra wrong submissions before accepted runs can make their penalties arbitrarily bad.

Then we scan upward from our original position. Every team above us that no longer strictly beats us is no longer counted before us.

Because the standings are sorted, once we find a team above us that still beats us, all teams above it also beat us.

---

### Computing the maximum possible place

We want as many teams as possible to become strictly better than us.

First, if our team is inside a block of tied teams, move it conceptually to the first position of that tie block. This is safe because tied teams are equal, but it allows the other tied teams to be considered as possible future overtakers.

Now process teams below us in groups with equal solved count.

Suppose our team solved `S_me` problems and a group solved `S_other`.

Define:

```text
det = S_me - S_other
```

Each team in this group needs:

- `det` balloons to reach our solved count;
- `det + 1` balloons to have more solved problems than us.

For every team in the group:

1. Simulate its cheapest `det` accepted problems.
2. If it now has smaller penalty than us, it can overtake us using `det` balloons.
3. Otherwise, if it has another unsolved problem, it can overtake us using `det + 1` balloons.

We greedily count cheaper overtakes first.

Since we process groups from higher solved count to lower solved count, the needed number of balloons never decreases.

---

### Complexity

Let:

```text
T <= 100  number of teams
P <= 26   number of problems
```

Each accept simulation scans at most `P` problems.

The complexity is easily within limits:

```text
O(T * P^2)
```

---

## 4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

struct Team {
    string name;
    int solved;
    long long penalty;
    int rank;

    // For every problem not solved before freeze,
    // store the number of previous wrong submissions.
    vector<int> unsolvedRejects;
};

int problemCount;
vector<Team> teams;
long long balloons;
string myTeamName;

bool readNonEmptyLine(string &line) {
    while (getline(cin, line)) {
        bool ok = false;
        for (char c : line) {
            if (!isspace((unsigned char)c)) {
                ok = true;
                break;
            }
        }
        if (ok) return true;
    }
    return false;
}

bool isTeamRow(const string &line) {
    // Team rows contain problem result symbols.
    // The balloon-count line contains only an integer.
    for (char c : line) {
        if (c == '.' || c == '+' || c == '-') {
            return true;
        }
    }
    return false;
}

Team parseTeamRow(const string &line) {
    Team t;

    int last = (int)line.size() - 1;

    auto skipSpaces = [&]() {
        while (last >= 0 && isspace((unsigned char)line[last])) {
            last--;
        }
    };

    auto readNumberBackwards = [&]() {
        long long value = 0;
        long long base = 1;

        while (last >= 0 && isdigit((unsigned char)line[last])) {
            value += base * (line[last] - '0');
            base *= 10;
            last--;
        }

        return value;
    };

    skipSpaces();

    // Parse problem result columns from right to left.
    for (int i = 0; i < problemCount; i++) {
        skipSpaces();

        // Optional number after '+' or '-'.
        // For '.', this will usually be 0.
        long long number = readNumberBackwards();

        skipSpaces();

        char sign = line[last];
        last--;

        // If the problem was not solved before the freeze,
        // it can possibly be solved in the last hour.
        if (sign != '+') {
            t.unsolvedRejects.push_back((int)number);
        }
    }

    skipSpaces();

    // Frozen penalty.
    t.penalty = readNumberBackwards();

    skipSpaces();

    // Frozen solved count.
    t.solved = (int)readNumberBackwards();

    // Now parse rank from the left.
    int start = 0;

    while (start < (int)line.size() && isspace((unsigned char)line[start])) {
        start++;
    }

    int rank = 0;

    while (start < (int)line.size() && isdigit((unsigned char)line[start])) {
        rank = rank * 10 + (line[start] - '0');
        start++;
    }

    while (start < (int)line.size() && isspace((unsigned char)line[start])) {
        start++;
    }

    // Remove spaces before the solved-count area.
    while (last >= start && isspace((unsigned char)line[last])) {
        last--;
    }

    t.rank = rank;
    t.name = line.substr(start, last - start + 1);

    return t;
}

bool readTestCase() {
    string line;

    // Read header.
    if (!readNonEmptyLine(line)) {
        return false;
    }

    {
        istringstream iss(line);
        string token;

        // Header starts with:
        // Rank Team = Penalty
        iss >> token >> token >> token >> token;

        problemCount = 0;

        // Remaining tokens are problem identifiers.
        while (iss >> token) {
            problemCount++;
        }
    }

    teams.clear();

    // Read standings rows until the balloon count.
    while (true) {
        if (!readNonEmptyLine(line)) {
            return false;
        }

        if (!isTeamRow(line)) {
            balloons = stoll(line);
            break;
        }

        teams.push_back(parseTeamRow(line));
    }

    // Read our team name.
    if (!readNonEmptyLine(line)) {
        return false;
    }

    int l = 0;
    int r = (int)line.size();

    while (l < r && isspace((unsigned char)line[l])) l++;
    while (r > l && isspace((unsigned char)line[r - 1])) r--;

    myTeamName = line.substr(l, r - l);

    return true;
}

bool betterThan(const Team &a, const Team &b) {
    if (a.solved != b.solved) {
        return a.solved > b.solved;
    }
    return a.penalty < b.penalty;
}

void acceptOne(Team &t) {
    auto it = min_element(t.unsolvedRejects.begin(), t.unsolvedRejects.end());

    int rejects = *it;

    t.solved++;
    t.penalty += 241 + 20LL * rejects;

    t.unsolvedRejects.erase(it);
}

int bestPlace(vector<Team> current, int myIndex, long long balloonsLeft) {
    Team &me = current[myIndex];

    // Give our team as many accepted problems as possible.
    while (balloonsLeft > 0 && !me.unsolvedRejects.empty()) {
        acceptOne(me);
        balloonsLeft--;
    }

    int n = (int)current.size();

    // Usually remaining balloons can be assigned harmlessly elsewhere.
    bool canBeAbsorbedElsewhere;

    if (myIndex != n - 1) {
        canBeAbsorbedElsewhere = true;
    } else if (myIndex == 0) {
        canBeAbsorbedElsewhere = true;
    } else {
        canBeAbsorbedElsewhere = current[myIndex - 1].solved < problemCount;
    }

    if (canBeAbsorbedElsewhere) {
        balloonsLeft = 0;
    }

    // Edge case used by the official solution:
    // unavoidable extra last-hour wrong submissions can only increase penalty.
    if (balloonsLeft > 0) {
        me.penalty += 20LL * balloonsLeft;
    }

    // Initially all teams above our row are assumed to be before us.
    int place = myIndex + 1;

    // Move upward while teams no longer beat our improved state.
    for (int i = myIndex - 1; i >= 0; i--) {
        if (betterThan(current[i], me)) {
            break;
        }
        place--;
    }

    return place;
}

int worstPlace(vector<Team> current, int myIndex, long long balloonsLeft) {
    int n = (int)current.size();

    // Put our team at the beginning of its tie block.
    // Tied teams have identical solved count and penalty.
    for (int i = myIndex - 1; i >= 0; i--) {
        if (current[i].rank != current[myIndex].rank) {
            break;
        }

        if (i == 0 || current[i - 1].rank != current[myIndex].rank) {
            swap(current[i], current[myIndex]);
            myIndex = i;
            break;
        }
    }

    Team &me = current[myIndex];

    int place = me.rank;

    int i = myIndex + 1;

    while (balloonsLeft > 0 && i < n) {
        int groupStart = i;

        // Find group with the same solved count.
        while (i < n && current[i].solved == current[groupStart].solved) {
            i++;
        }

        int groupEnd = i;

        int det = me.solved - current[groupStart].solved;

        // If even one team in this group cannot reach our solved count,
        // all later groups are also impossible.
        if (balloonsLeft < det) {
            break;
        }

        // Simulate cheapest det accepted problems for every team in this group.
        for (int j = groupStart; j < groupEnd; j++) {
            for (int k = 0; k < det; k++) {
                acceptOne(current[j]);
            }
        }

        // First count teams that overtake with exactly det balloons.
        for (int j = groupStart; j < groupEnd && balloonsLeft >= det; j++) {
            if (betterThan(current[j], me)) {
                balloonsLeft -= det;
                place++;
            }
        }

        // Then count teams that need one additional solved problem.
        for (int j = groupStart; j < groupEnd && balloonsLeft >= det + 1; j++) {
            if (!betterThan(current[j], me) && !current[j].unsolvedRejects.empty()) {
                balloonsLeft -= det + 1;
                acceptOne(current[j]);
                place++;
            }
        }
    }

    return place;
}

void solveTestCase() {
    int myIndex = -1;

    for (int i = 0; i < (int)teams.size(); i++) {
        if (teams[i].name == myTeamName) {
            myIndex = i;
            break;
        }
    }

    int minimumPlace = bestPlace(teams, myIndex, balloons);
    int maximumPlace = worstPlace(teams, myIndex, balloons);

    cout << minimumPlace << ' ' << maximumPlace << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while (readTestCase()) {
        solveTestCase();
    }

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys
from dataclasses import dataclass
from typing import List


@dataclass
class Team:
    name: str
    solved: int
    penalty: int
    rank: int

    # For every problem not solved before freeze,
    # store previous wrong submissions.
    unsolved_rejects: List[int]


def better_than(a: Team, b: Team) -> bool:
    """
    Return True if team a is strictly better than team b.
    """
    if a.solved != b.solved:
        return a.solved > b.solved
    return a.penalty < b.penalty


def clone_teams(teams: List[Team]) -> List[Team]:
    """
    Copy teams.

    Only unsolved_rejects is mutable, so it must be copied separately.
    """
    return [
        Team(t.name, t.solved, t.penalty, t.rank, t.unsolved_rejects[:])
        for t in teams
    ]


def accept_one(team: Team) -> None:
    """
    Simulate one accepted problem in the last hour.

    To minimize penalty, solve the unsolved problem with the fewest
    previous wrong submissions.
    """
    idx = min(range(len(team.unsolved_rejects)),
              key=lambda i: team.unsolved_rejects[i])

    rejects = team.unsolved_rejects[idx]

    team.solved += 1
    team.penalty += 241 + 20 * rejects

    team.unsolved_rejects.pop(idx)


def parse_team_row(line: str, problem_count: int) -> Team:
    """
    Parse a standings row.

    Since team names may contain spaces and digits, parse structured fields
    from the right side.
    """
    last = len(line) - 1

    def skip_spaces():
        nonlocal last
        while last >= 0 and line[last].isspace():
            last -= 1

    def read_number_backwards() -> int:
        nonlocal last

        value = 0
        base = 1

        while last >= 0 and line[last].isdigit():
            value += base * int(line[last])
            base *= 10
            last -= 1

        return value

    skip_spaces()

    unsolved_rejects = []

    # Parse problem columns from right to left.
    for _ in range(problem_count):
        skip_spaces()

        # Optional number after '+' or '-'.
        number = read_number_backwards()

        skip_spaces()

        sign = line[last]
        last -= 1

        # Only unsolved problems can be solved during the last hour.
        if sign != '+':
            unsolved_rejects.append(number)

    skip_spaces()

    penalty = read_number_backwards()

    skip_spaces()

    solved = read_number_backwards()

    # Parse rank from the left.
    start = 0

    while start < len(line) and line[start].isspace():
        start += 1

    rank = 0

    while start < len(line) and line[start].isdigit():
        rank = rank * 10 + int(line[start])
        start += 1

    while start < len(line) and line[start].isspace():
        start += 1

    # Trim spaces before the solved-count area.
    while last >= start and line[last].isspace():
        last -= 1

    name = line[start:last + 1]

    return Team(name, solved, penalty, rank, unsolved_rejects)


def is_team_row(line: str) -> bool:
    """
    A team row contains at least one problem result symbol.
    The balloon count line does not.
    """
    return any(c in ".+-" for c in line)


def best_place(original_teams: List[Team],
               my_index: int,
               balloons: int,
               problem_count: int) -> int:
    """
    Compute the minimum possible final place.
    """
    teams = clone_teams(original_teams)

    me = teams[my_index]
    balloons_left = balloons

    # Give our team as many solves as possible.
    while balloons_left > 0 and me.unsolved_rejects:
        accept_one(me)
        balloons_left -= 1

    n = len(teams)

    # Usually leftover balloons can be assigned harmlessly elsewhere.
    if my_index != n - 1:
        can_be_absorbed_elsewhere = True
    elif my_index == 0:
        can_be_absorbed_elsewhere = True
    else:
        can_be_absorbed_elsewhere = teams[my_index - 1].solved < problem_count

    if can_be_absorbed_elsewhere:
        balloons_left = 0

    # Edge handling from the standard solution:
    # forced extra wrong submissions only increase our penalty.
    if balloons_left > 0:
        me.penalty += 20 * balloons_left

    # Initially, all rows above our row are assumed to be before us.
    place = my_index + 1

    # Move upward while teams above no longer beat us.
    i = my_index - 1

    while i >= 0 and not better_than(teams[i], me):
        place -= 1
        i -= 1

    return place


def worst_place(original_teams: List[Team],
                my_index: int,
                balloons: int) -> int:
    """
    Compute the maximum possible final place.
    """
    teams = clone_teams(original_teams)
    n = len(teams)

    # Move our team to the first position of its tie-rank block.
    i = my_index - 1

    while i >= 0 and teams[i].rank == teams[my_index].rank:
        if i == 0 or teams[i - 1].rank != teams[my_index].rank:
            teams[i], teams[my_index] = teams[my_index], teams[i]
            my_index = i
            break
        i -= 1

    me = teams[my_index]

    place = me.rank
    balloons_left = balloons

    i = my_index + 1

    while balloons_left > 0 and i < n:
        group_start = i

        # Group teams with the same frozen solved count.
        while i < n and teams[i].solved == teams[group_start].solved:
            i += 1

        group_end = i

        det = me.solved - teams[group_start].solved

        # If this group cannot even reach our solved count,
        # no later group can either.
        if balloons_left < det:
            break

        # Give every team in this group its cheapest det solves.
        for j in range(group_start, group_end):
            for _ in range(det):
                accept_one(teams[j])

        # First count teams that overtake using exactly det balloons.
        for j in range(group_start, group_end):
            if balloons_left >= det and better_than(teams[j], me):
                balloons_left -= det
                place += 1

        # Then count teams that need det + 1 balloons.
        for j in range(group_start, group_end):
            if balloons_left >= det + 1:
                if not better_than(teams[j], me) and teams[j].unsolved_rejects:
                    balloons_left -= det + 1
                    accept_one(teams[j])
                    place += 1

    return place


def solve_all() -> None:
    lines = sys.stdin.read().splitlines()
    ptr = 0
    output = []

    def read_non_empty_line():
        nonlocal ptr

        while ptr < len(lines):
            line = lines[ptr]
            ptr += 1

            if any(not c.isspace() for c in line):
                return line

        return None

    while True:
        header = read_non_empty_line()

        if header is None:
            break

        tokens = header.split()

        # Header is:
        # Rank Team = Penalty problem1 problem2 ...
        problem_count = len(tokens) - 4

        teams = []

        # Read standings rows.
        while True:
            line = read_non_empty_line()

            if line is None:
                return

            if not is_team_row(line):
                balloons = int(line.strip())
                break

            teams.append(parse_team_row(line, problem_count))

        my_team_name = read_non_empty_line()

        if my_team_name is None:
            return

        my_team_name = my_team_name.strip()

        my_index = -1

        for i, team in enumerate(teams):
            if team.name == my_team_name:
                my_index = i
                break

        minimum_place = best_place(
            teams,
            my_index,
            balloons,
            problem_count
        )

        maximum_place = worst_place(
            teams,
            my_index,
            balloons
        )

        output.append(f"{minimum_place} {maximum_place}")

    print("\n".join(output))


if __name__ == "__main__":
    solve_all()
```