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

364. Lemmings
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



N lemmings appear in the point A(x, h) one after another with interval of s seconds. Lemmings always go forward, they can't go backward, but can change their direction. Lemmings are not really smart and always use the same algorithm: they either drop down with velocity 1 cm/sec, if they do not touch a platform, or walk on the platform forward with velocity 1 cm/sec, until reaching the end of the platform (platforms are the horizontal segments that do not intersect, do not collide and do not touch each other). Newly appeared lemming has direction to the right (thus, to the positive direction of x-axis). Lemming may finish its movement either in infinite falling down or at the home located at the point (a, b) on some platform. Reaching home is ultimate goal for each lemming.

You need to maximize amount of lemmings that reach home, and to minimize time when the last lemming reaches home. You may perform only one action: choose any lemming that is moving by the platform now (or have just fallen down to the platform), and stop it. If the lemming was stopped it will stay at its place forever, and all lemmings touched it (either dropped or came from either side) will reverse their direction. Point A doesn't touch any platform.

Input
The first line of the input file contains two integer numbers N and s (1 ≤ N ≤ 100; 1 ≤ s ≤ 10). Next line contains four numbers x, h, a, b - coordinates of the point A and of the home (0 ≤ x, h, a, b ≤ 10000). Third line contains the number of platforms M (1 ≤ M ≤ 100). Next M lines describe platforms. Platform description consists of three numbers l, r and h, where (l, h) is the left end of the platform and (r, h) is the right end of the platform (0 ≤ l, r, h ≤ 10000; l < r). It is guaranteed that after falling from any platform lemming either infinitely falling or falls to the inner point of some platform. All numbers in the input file are integer.

Output
Print two integer numbers in the output file: K - maximal possible number of lemmings reached the home, and T - minimal time of reaching the home of the last lemming. First lemming appears at the 0 time moment. If no one lemming can reach the home, print 0 0.

Example(s)
sample input
sample output
100 5
6 5 6 0
4
1 2 4
4 7 4
3 5 2
0 6 0
98 504

Notes to the example
It is necessary to stop first two lemmings at points (6, 4) and (4, 2) respectively.

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

There are `N` lemmings. They appear at point `A(x, h)` one by one, every `s` seconds. Each lemming initially moves to the right.

A lemming:

- falls vertically down with speed `1` if not on a platform,
- walks horizontally on a platform with speed `1`,
- falls from a platform end,
- may eventually reach the home point `(a, b)` located on some platform, or fall forever.

We may stop lemmings on platforms. A stopped lemming stays forever and acts as a reflector: any later lemming touching it reverses direction.

We need to:

1. maximize the number of lemmings that reach home,
2. among such strategies, minimize the time when the last successful lemming reaches home.

If no lemming can reach home, output `0 0`.

---

## 2. Key observations needed to solve the problem

### Observation 1 — We may stop multiple lemmings

The statement wording is slightly misleading, but the sample requires stopping two lemmings. The intended meaning is:

> The only type of action allowed is stopping a lemming.

We may perform this action multiple times.

Each stopped lemming becomes one permanent reflector and cannot reach home.

So if a route needs `S` stopped lemmings, then at most:

```text
N - S
```

lemmings can reach home.

Therefore:

- maximizing successful lemmings is equivalent to minimizing the number of reflectors,
- among routes using the minimum number of reflectors, we minimize travel time.

---

### Observation 2 — A stopped lemming is just a direction reversal point

Once a lemming is stopped, all later lemmings reverse direction when they touch it.

So a route from the start to home can be described as a path where, on some platforms, the lemming may reverse direction.

Each reversal costs exactly one stopped lemming.

---

### Observation 3 — On one platform, only two choices matter

Suppose a lemming lands on platform `p` at coordinate `ex`, moving in direction `dir`.

There are only two useful actions:

#### 1. Do not reverse

The lemming walks to the end of the platform in its current direction and falls.

Cost:

```text
0 extra reflectors
```

#### 2. Reverse immediately at `ex`

Place a reflector at the landing point. The lemming reverses and walks to the opposite end.

Cost:

```text
1 extra reflector
```

Reversing later on the same platform is never better because:

- it still costs one reflector,
- it adds unnecessary walking distance.

---

### Observation 4 — Falling always moves to a lower platform

After falling from a platform end, the lemming either falls forever or lands on the highest platform strictly below that contains the falling `x` coordinate in its interior.

Since heights strictly decrease after every fall, the movement graph is acyclic.

Therefore, we can process platforms in descending order of height.

---

### Observation 5 — Use lexicographic optimization

For every reachable state, we store:

```text
(number of reflectors used, total travel distance)
```

A smaller pair is better:

1. fewer reflectors is better,
2. if equal, shorter distance is better.

---

## 3. Full solution approach based on the observations

### State definition

A state is:

```text
(platform, entry_x, direction)
```

where:

- `platform` is the current platform index,
- `entry_x` is the x-coordinate where the lemming landed on this platform,
- `direction` is:
  - `1` for right,
  - `-1` for left.

For each state we store the best pair:

```text
(reflectors_used, distance_so_far)
```

---

### Finding the next platform below

When falling vertically from x-coordinate `fx` and height `from_h`, we need the highest platform below `from_h` such that:

```text
platform_height < from_h
platform_left < fx < platform_right
```

The strict inequality is important because a falling lemming lands only on the interior of a platform.

If no such platform exists, the lemming falls forever.

Since `M <= 100`, we can simply scan all platforms each time.

---

### Initialization

The first lemming appears at `(x, h)` and falls vertically.

We find the first platform below `(x, h)`.

If such platform exists, initial state is:

```text
(platform, x, right)
```

with cost:

```text
(0 reflectors, h - platform_height distance)
```

If no platform is found, no route is possible.

---

### Transitions from a state

Assume we are in state:

```text
(platform p, entry_x ex, direction dir)
```

with cost:

```text
(turns, dist)
```

Let:

```text
forward_end = right end if dir = 1, else left end
back_end    = left end if dir = 1, else right end
```

There are two transitions.

---

#### Transition 1 — Continue forward

Walk to `forward_end`, then fall.

New cost:

```text
turns unchanged
dist + abs(forward_end - ex) + fall_distance
```

Direction remains `dir`.

---

#### Transition 2 — Reverse immediately

Use one reflector at `ex`.

Walk to `back_end`, then fall.

New cost:

```text
turns + 1
dist + abs(back_end - ex) + fall_distance
```

Direction becomes `-dir`.

---

### Reaching home

Whenever we process a state on the home platform, we check whether the lemming can reach home from `entry_x`.

Let:

```text
diff = a - entry_x
```

If home is in the current direction, no extra reflector is needed:

```text
diff * direction >= 0
```

Otherwise, we need one extra reflector at the entry point.

The distance added is always:

```text
abs(a - entry_x)
```

We update the best answer with the resulting pair.

---

### Final answer

Let the best route require:

```text
S reflectors
D seconds of travel time
```

Since each reflector costs one stopped lemming, the number of successful lemmings is:

```text
K = N - S
```

If:

```text
S >= N
```

then no lemming remains to reach home, so output:

```text
0 0
```

Otherwise, the last successful lemming is the `N`-th lemming, which appears at time:

```text
(N - 1) * s
```

Then it needs `D` seconds to reach home.

So:

```text
T = (N - 1) * s + D
```

---

### Complexity

There are at most `100` platforms.

For each reachable state, we try two transitions, and each transition scans all platforms to find the next one below.

The number of states is small, bounded by platform endpoints and the starting x-coordinate.

Complexity is easily within limits:

```text
O(number_of_states * M)
```

with `M <= 100`.

---

## 4. C++ implementation with detailed comments

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

struct Platform {
    int l, r, h;
};

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

    int N, s;
    cin >> N >> s;

    int x, h, a, b;
    cin >> x >> h >> a >> b;

    int M;
    cin >> M;

    vector<Platform> p(M);

    for (int i = 0; i < M; i++) {
        cin >> p[i].l >> p[i].r >> p[i].h;
    }

    /*
        Finds the highest platform strictly below height from_h
        whose interior contains x-coordinate fx.
    */
    auto next_below = [&](int fx, int from_h) {
        int best = -1;

        for (int i = 0; i < M; i++) {
            if (p[i].h < from_h && p[i].l < fx && fx < p[i].r) {
                if (best == -1 || p[i].h > p[best].h) {
                    best = i;
                }
            }
        }

        return best;
    };

    /*
        Find the platform containing the home.
        The home may be at an endpoint, so we use <=.
    */
    int home_platform = -1;

    for (int i = 0; i < M; i++) {
        if (p[i].h == b && p[i].l <= a && a <= p[i].r) {
            home_platform = i;
            break;
        }
    }

    /*
        Process platforms from highest to lowest.
        Since every fall strictly decreases height, this is a topological order.
    */
    vector<int> order(M);
    iota(order.begin(), order.end(), 0);

    sort(order.begin(), order.end(), [&](int i, int j) {
        return p[i].h > p[j].h;
    });

    /*
        arrivals[platform] stores reachable states on this platform.

        Key:
            pair(entry_x, direction)

        direction:
             1 means moving right
            -1 means moving left

        Value:
            pair(reflectors_used, distance)

        Costs are compared lexicographically.
    */
    vector<map<pair<int, int>, pair<int, int>>> arrivals(M);

    /*
        Initial fall from point A(x, h).
    */
    int start_platform = next_below(x, h);

    if (start_platform != -1) {
        int initial_distance = h - p[start_platform].h;

        // The newly appeared lemming initially moves to the right.
        arrivals[start_platform][{x, 1}] = {0, initial_distance};
    }

    const int INF = 1e9;

    int best_reflectors = INF;
    int best_distance = INF;

    /*
        Dynamic programming over platforms.
    */
    for (int plat : order) {
        for (auto item : arrivals[plat]) {
            int entry_x = item.first.first;
            int dir = item.first.second;

            int reflectors = item.second.first;
            int dist = item.second.second;

            /*
                If this is the home platform, try to finish here.
            */
            if (plat == home_platform) {
                int diff = a - entry_x;

                int extra_reflector = 0;

                /*
                    If home is behind the current direction,
                    we need one reflector at the entry point.
                */
                if (1LL * diff * dir < 0) {
                    extra_reflector = 1;
                }

                int candidate_reflectors = reflectors + extra_reflector;
                int candidate_distance = dist + abs(diff);

                if (make_pair(candidate_reflectors, candidate_distance) <
                    make_pair(best_reflectors, best_distance)) {
                    best_reflectors = candidate_reflectors;
                    best_distance = candidate_distance;
                }
            }

            /*
                Determine the two useful exits from this platform.
            */
            int forward_end;
            int backward_end;

            if (dir == 1) {
                forward_end = p[plat].r;
                backward_end = p[plat].l;
            } else {
                forward_end = p[plat].l;
                backward_end = p[plat].r;
            }

            /*
                Move 1:
                Continue forward, no new reflector.
            */
            {
                int end_x = forward_end;
                int new_dir = dir;
                int new_reflectors = reflectors;

                int below = next_below(end_x, p[plat].h);

                if (below != -1) {
                    int new_distance =
                        dist +
                        abs(end_x - entry_x) +
                        (p[plat].h - p[below].h);

                    pair<int, int> state = {end_x, new_dir};
                    pair<int, int> cost = {new_reflectors, new_distance};

                    auto it = arrivals[below].find(state);

                    if (it == arrivals[below].end() || cost < it->second) {
                        arrivals[below][state] = cost;
                    }
                }
            }

            /*
                Move 2:
                Reverse immediately at entry_x, using one reflector.
            */
            {
                int end_x = backward_end;
                int new_dir = -dir;
                int new_reflectors = reflectors + 1;

                int below = next_below(end_x, p[plat].h);

                if (below != -1) {
                    int new_distance =
                        dist +
                        abs(end_x - entry_x) +
                        (p[plat].h - p[below].h);

                    pair<int, int> state = {end_x, new_dir};
                    pair<int, int> cost = {new_reflectors, new_distance};

                    auto it = arrivals[below].find(state);

                    if (it == arrivals[below].end() || cost < it->second) {
                        arrivals[below][state] = cost;
                    }
                }
            }
        }
    }

    /*
        If no route exists, or if all lemmings must be sacrificed,
        nobody can reach home.
    */
    if (best_reflectors == INF || best_reflectors >= N) {
        cout << "0 0\n";
        return 0;
    }

    int successful = N - best_reflectors;

    long long last_time = 1LL * (N - 1) * s + best_distance;

    cout << successful << ' ' << last_time << '\n';

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys


def solve():
    data = list(map(int, sys.stdin.read().split()))
    idx = 0

    # Number of lemmings and interval between appearances.
    n = data[idx]
    s = data[idx + 1]
    idx += 2

    # Start point A(x, h), home point (a, b).
    x = data[idx]
    h = data[idx + 1]
    a = data[idx + 2]
    b = data[idx + 3]
    idx += 4

    # Platforms.
    m = data[idx]
    idx += 1

    platforms = []

    for _ in range(m):
        l = data[idx]
        r = data[idx + 1]
        ph = data[idx + 2]
        idx += 3
        platforms.append((l, r, ph))

    def next_below(fx, from_h):
        """
        Find the highest platform strictly below from_h
        whose interior contains x-coordinate fx.
        """
        best = -1

        for i, (l, r, ph) in enumerate(platforms):
            if ph < from_h and l < fx < r:
                if best == -1 or ph > platforms[best][2]:
                    best = i

        return best

    # Find the platform containing the home point.
    home_platform = -1

    for i, (l, r, ph) in enumerate(platforms):
        if ph == b and l <= a <= r:
            home_platform = i
            break

    # Platforms processed from highest to lowest.
    order = sorted(range(m), key=lambda i: -platforms[i][2])

    """
    arrivals[p] is a dictionary of states on platform p.

    Key:
        (entry_x, direction)

    direction:
         1 means moving right
        -1 means moving left

    Value:
        (reflectors_used, distance)

    Python compares tuples lexicographically, which is exactly what we need.
    """
    arrivals = [dict() for _ in range(m)]

    # Initial fall from A(x, h).
    start_platform = next_below(x, h)

    if start_platform != -1:
        start_height = platforms[start_platform][2]
        initial_distance = h - start_height

        # New lemmings initially move to the right.
        arrivals[start_platform][(x, 1)] = (0, initial_distance)

    INF = 10**18

    best_reflectors = INF
    best_distance = INF

    # Dynamic programming over the DAG of platforms.
    for plat in order:
        l, r, ph = platforms[plat]

        # Transitions only go downward, so this platform will not be updated again.
        for (entry_x, direction), (reflectors, dist) in list(arrivals[plat].items()):

            # Try finishing at home if we are on the home platform.
            if plat == home_platform:
                diff = a - entry_x

                # If home is behind, one extra reflector is needed.
                if diff * direction >= 0:
                    extra_reflector = 0
                else:
                    extra_reflector = 1

                candidate_reflectors = reflectors + extra_reflector
                candidate_distance = dist + abs(diff)

                if (candidate_reflectors, candidate_distance) < (
                    best_reflectors,
                    best_distance,
                ):
                    best_reflectors = candidate_reflectors
                    best_distance = candidate_distance

            # Determine forward and backward ends.
            if direction == 1:
                forward_end = r
                backward_end = l
            else:
                forward_end = l
                backward_end = r

            moves = [
                # Continue forward: no new reflector.
                (forward_end, direction, reflectors),

                # Reverse immediately: one new reflector.
                (backward_end, -direction, reflectors + 1),
            ]

            for end_x, new_direction, new_reflectors in moves:
                below = next_below(end_x, ph)

                # If no platform below, this route falls forever.
                if below == -1:
                    continue

                below_height = platforms[below][2]

                new_distance = (
                    dist
                    + abs(end_x - entry_x)
                    + (ph - below_height)
                )

                state = (end_x, new_direction)
                cost = (new_reflectors, new_distance)

                old = arrivals[below].get(state)

                if old is None or cost < old:
                    arrivals[below][state] = cost

    # No path, or all lemmings would have to be stopped.
    if best_reflectors == INF or best_reflectors >= n:
        print("0 0")
        return

    successful = n - best_reflectors

    # The last lemming appears at time (n - 1) * s.
    last_time = (n - 1) * s + best_distance

    print(successful, last_time)


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