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

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, s;
int x, h, a, b;
int m;
vector<int> pl, pr, ph;

void read() {
    cin >> n >> s;
    cin >> x >> h >> a >> b;
    cin >> m;
    pl.assign(m, 0);
    pr.assign(m, 0);
    ph.assign(m, 0);
    for(int i = 0; i < m; i++) {
        cin >> pl[i] >> pr[i] >> ph[i];
    }
}

int next_below(int fx, int from_h) {
    int best = -1;
    for(int i = 0; i < m; i++) {
        if(ph[i] < from_h && pl[i] < fx && fx < pr[i]) {
            if(best == -1 || ph[i] > ph[best]) {
                best = i;
            }
        }
    }

    return best;
}

void solve() {
    // The statement says we may stop "only one" lemming, but the sample stops
    // the first two, so that phrase is a mistranslation: we may stop as many
    // lemmings as we like. A stopped lemming becomes a permanent point that
    // reverses anyone who touches it, so the real task is to pick the fewest
    // lemmings to sacrifice as reflectors so that every later (identical)
    // lemming is guided from A into the home (a, b). The first S lemmings build
    // the reflectors - lemming i runs with reflectors 1..i-1 already in place
    // and is stopped exactly at the i-th turn it would make - so any reflector
    // set lying on the target trajectory is realizable, and S sacrifices leave
    // K = N - S survivors that all reach home along one fixed path of length D,
    // the last of them appearing at (N-1)*s, so T = (N-1)*s + D.
    //
    // A lemming falls straight down (x fixed) until it lands on the highest
    // platform strictly below it, then walks until the platform's end or a
    // reflector. On a platform entered at ex with direction d there are only
    // two useful moves:
    //
    // - no turn (cost 0): walk to the forward end and drop off it keeping d,
    // - one turn (cost 1): drop a reflector right at ex, reverse, and walk to
    //   the far end, dropping off it with direction -d; cheapest walk is the
    //   full |ex - far_end|.
    //
    // A state is therefore (platform, entry x, direction): the exit end and
    // hence the next platform depend only on the direction and the turn choice,
    // while the walked distances depend on ex. Every fall strictly lowers the
    // height, so the state graph is a DAG whose topological order is just the
    // platforms by descending height; visiting them in that order means each
    // state is finalized before it is expanded, so a single relaxation pass on
    // the lexicographic cost (turns, distance) yields, for every state, the
    // fewest turns and then the shortest distance to reach it. Landing on the
    // home platform reaches home for free when a lies forward of ex and for one
    // extra turn when it lies behind, each adding the walk |a - ex|. The
    // lexicographic minimum over all home arrivals is (S, D); if home is never
    // reached, or S >= N, nobody makes it.

    int home_plat = -1;
    for(int i = 0; i < m; i++) {
        if(ph[i] == b && pl[i] <= a && a <= pr[i]) {
            home_plat = i;
        }
    }

    vector<int> order(m);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
        return ph[i] > ph[j];
    });

    vector<map<pair<int, int>, pair<int, int>>> arrival(m);

    int start = next_below(x, h);
    int answer_s = INT_MAX, answer_d = INT_MAX;

    if(start != -1) {
        arrival[start][{x, 1}] = {0, h - ph[start]};
    }

    for(int plat: order) {
        for(auto& [state, cost]: arrival[plat]) {
            auto [ex, dir] = state;
            auto [turns, dist] = cost;

            if(plat == home_plat) {
                int diff = a - ex;
                int reach_turns = turns + ((int64_t)diff * dir >= 0 ? 0 : 1);
                int reach_dist = dist + abs(diff);
                if(make_pair(reach_turns, reach_dist) <
                   make_pair(answer_s, answer_d)) {
                    answer_s = reach_turns;
                    answer_d = reach_dist;
                }
            }

            int forward_end = dir > 0 ? pr[plat] : pl[plat];
            int back_end = dir > 0 ? pl[plat] : pr[plat];

            int moves[2][3] = {
                {forward_end, dir, turns}, {back_end, -dir, turns + 1}
            };

            for(auto& mv: moves) {
                int end_x = mv[0], new_dir = mv[1], new_turns = mv[2];
                int nb = next_below(end_x, ph[plat]);
                if(nb == -1) {
                    continue;
                }

                int new_dist = dist + abs(end_x - ex) + (ph[plat] - ph[nb]);
                auto key = make_pair(end_x, new_dir);
                auto jt = arrival[nb].find(key);
                if(jt == arrival[nb].end() ||
                   make_pair(new_turns, new_dist) < jt->second) {
                    arrival[nb][key] = {new_turns, new_dist};
                }
            }
        }
    }

    if(answer_s == INT_MAX || answer_s >= n) {
        cout << "0 0" << '\n';
        return;
    }

    cout << n - answer_s << ' ' << (int64_t)(n - 1) * s + answer_d << '\n';
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    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()
```
