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

475. Be a Smart Raftsman
Time limit per test: 1.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



On Halloween, when other people are gathering to tell terrifying stories (see problem H. "Hero of our time"), to torment poor pumpkins (see problem J. "Jealous Cucumber"), to create demonic teams (see problem C. "Coach's Trouble"), in other words, to do all that stuff, you don't want to be ordinary, so now you are planning to try some extreme sports. Rafting would be the best choise, because when water is cold enough (as it is now!) rafting is extremely extreme.


You are members of a rafting crew which consists of n participants. You navigate the river, and your goal is to pass m consecutive riffles and to get from the start to the finish as soon as possible. The i-th riffle is characterized by critical weight ci, and the j-th participant is characterized by his or her weight wj. If your raft goes through the i-th riffle with people on board with total weight exceeding ci, it capsizes. This part of rafting is the most exciting, but it requires additional time to get on the raft after capsize. So sometimes it is better to take a group of people with total weight not exceeding critical weight on the raft, while others pass the distance by foot.


More formally, consider m + 1 points p0, p1,..., pm, where p0 is the start and pm is the finish. Each of the intermediate points pi (1 ≤ i ≤ m-1) is located between the i-th and (i + 1)-th riffle. It takes Di minutes for the raft to get from pi-1 to pi, if it passes the i-th riffle with capsize, and di minutes otherwise. The j-th participant can get from pi-1 to pi in tj minutes by foot. It takes him or her sj minutes to get on the raft or to get off the raft on the bank. Before each of the riffles your group is divided into two parts. The first part rafts through the riffle (with or without capsize), and the second part goes on the bank to the next intermediate point. At this point they always wait for the raft, or the raft waits for all the walkers, if it arrives sooner. Then some participants who are on the raft can get off, and some participants who are on the bank can get on the raft. They can't start doing it before the raft and all the walkers arrive to the point. The total time required for this action is equal to the sum of sj for people changing their place. Then you pass the next riffle and so on, until you get to the finish. Note that no one can start moving to the next point until others have changed places.


Remember, that you start at the point p0 having all your group on the bank (not on the raft), and you must finish at the point pm also with all participants on the bank and the raft with you. You are not allowed to leave the raft at the start or at some intermediate point, and walk to the finish without it. You can take all the group to the raft to pass a riffle, but you can't leave the raft empty during the trip. Your task is to calculate the minimal time required to reach the finish.

Input
The first line of the input contains two numbers n and m (1 ≤ n ≤ 10, 1 ≤ m ≤ 1000). Following n lines describe participants. Each of them consists of three integers wj, tj, sj. Following m lines also contains three integers each — ci, Di and di for the i-th riffle. All numbers in the input are positive integers not exceeding 10000.

Output
Output the minimal time.

Example(s)
sample input
sample output
2 3
50 5 1
70 20 1
30 15 10
60 100 10
70 100 10
51

<|response|>
## 1) Abridged problem statement (concise)

There are **n ≤ 10** participants and **m ≤ 1000** consecutive river segments (riffles) between points \(p_0 \to p_1 \to \dots \to p_m\).

For riffle \(i\):
- If total weight of people **on the raft** exceeds \(c_i\), the raft **capsizes** and travel time is \(D_i\).
- Otherwise travel time is \(d_i\).

Each participant \(j\):
- If they **walk** a segment, it takes \(t_j\) minutes.
- Each time they **change** between raft and bank (get on or off), it costs \(s_j\) minutes.

Before each riffle, choose who rides and who walks. Everyone arrives at the next point and waits for the slowest (raft vs. slowest walker). Then you may swap people (paying sum of \(s_j\) for those who changed side). The raft must **never travel empty**.

Start at \(p_0\) with everyone on the bank (`mask=0`). Finish at \(p_m\) with everyone on the bank (`mask=0`). Find the **minimum total time**.

---

## 2) Key observations

1. **State = set of people on the raft.**
   Only the composition of the raft matters at each point \(p_i\). With \(n \le 10\), represent it as a bitmask `mask` in \([0, 2^n)\).

2. **Segment time for a fixed mask is easy:**
   - Raft time is \(D_i\) if \(W(mask) > c_i\), else \(d_i\).
   - Walkers are those not in `mask`, and they walk in parallel, so walking time is
     \(\max_{j \notin mask} t_j\) (0 if nobody walks).
   - Everyone must wait:
     \[
     T(i,mask)=\max(\text{raftTime}, \text{maxWalkTime})
     \]

3. **Swapping at a point is a shortest-path problem on masks.**
   From mask `u`, toggling person `j` leads to `v = u ^ (1<<j)` with cost \(s_j\).
   You can do multiple swaps in any order → cycles exist → use **Dijkstra** to compute the minimal "swap-adjusted" time for all masks at that point.

4. **Process riffles one by one (DP over points), but run Dijkstra at each point.**
   For each riffle, first allow any swaps (Dijkstra), then traverse the riffle (add segment time).

---

## 3) Full solution approach

Let \(N = 2^n \le 1024\).

### Precompute for every mask
- `sum_w[mask]` = total weight on raft.
- `max_out[mask]` = maximum walking time among people **not** on raft (0 if all on raft).

This makes each segment cost computation \(O(1)\).

### DP meaning
`prev[mask]` = minimal time to be at point \(p_{i}\) (current point) with exactly `mask` on the raft.

Initialization:
- At start \(p_0\): `prev[0] = 0` (everyone on bank), others = INF.

### At each riffle i (from 0 to m-1)
1. **Allow arbitrary swaps at point \(p_i\):**
   Run Dijkstra on the mask graph with initial distances `dist = prev`.
   After Dijkstra, `dist[mask]` is the best time to be at \(p_i\) and ready to depart with raft set `mask`.

2. **Traverse riffle i with non-empty mask:**
   Raft cannot travel empty, so only `mask != 0` allowed.
   \[
   next[mask] = dist[mask] + \max(\text{raftTime}(i,mask), max\_out[mask])
   \]

3. Set `prev = next` and continue.

### Finish condition
After processing all riffles, we are at \(p_m\) with some `prev[mask]`.
We must end with everyone on bank: `mask=0`. So run **one final Dijkstra** (swaps at finish) starting from `prev`, and output `dist[0]`.

### Complexity
- Masks: \(N \le 1024\).
- Dijkstra per point: nodes \(N\), edges \(N \cdot n\) (toggle one bit), complexity \(O(N n \log N)\).
- Runs: \(m\) times + 1 final.

Total: \(O((m+1) N n \log N)\), easily fits.

---

## 4) C++ implementation (detailed comments)

```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;
};

const int64_t inf = (int64_t)1e18 + 42;

int n, m;
vector<int> w, t, s;
vector<int> c, D, d;

void read() {
    cin >> n >> m;
    w.resize(n);
    t.resize(n);
    s.resize(n);
    for(int j = 0; j < n; j++) {
        cin >> w[j] >> t[j] >> s[j];
    }
    c.resize(m);
    D.resize(m);
    d.resize(m);
    for(int i = 0; i < m; i++) {
        cin >> c[i] >> D[i] >> d[i];
    }
}

void solve() {
    // We first notice that n <= 10, meaning that something like 2^n is feasible
    // as one of the terms in the complexity. That matches the unique sets that
    // can be in the boat at any time, meaning we can try to encode the full
    // state. Particularly, the set is defined by the people currently in the
    // boat, and the current raft we are at. At every moment we can either
    // remove or add some people to the mask, or proceed to the next raft. This
    // is O(n) transitions which is sufficiently small, but the issue is that we
    // can't do DP as there are cycles (due to the mask transitions). However,
    // we can think of this as a graph problem instead, with states being the
    // same. Then running Dijkstra would be sufficiently fast for the given
    // constraints. There are just some details in terms of the transitions.
    // One small optimization is to do M independent runs of Dijkstra over the
    // 2^n dimension, as that's the only place where we could have cycles.

    int N = 1 << n;
    vector<int> sum_w(N), max_out(N);
    for(int mask = 0; mask < N; mask++) {
        int sw = 0, mo = 0;
        for(int j = 0; j < n; j++) {
            if(mask & (1 << j)) {
                sw += w[j];
            } else {
                mo = max(mo, t[j]);
            }
        }
        sum_w[mask] = sw;
        max_out[mask] = mo;
    }

    vector<int64_t> prev_dp(N, inf);
    prev_dp[0] = 0;

    auto run_dijkstra = [&](vector<int64_t>& dist) {
        priority_queue<
            pair<int64_t, int>, vector<pair<int64_t, int>>, greater<>>
            pq;
        for(int mask = 0; mask < N; mask++) {
            if(dist[mask] < inf) {
                pq.push({dist[mask], mask});
            }
        }
        while(!pq.empty()) {
            int64_t time = pq.top().first;
            int umask = pq.top().second;
            pq.pop();
            if(time > dist[umask]) {
                continue;
            }
            for(int j = 0; j < n; j++) {
                int vmask = umask ^ (1 << j);
                int64_t new_time = time + s[j];
                if(new_time < dist[vmask]) {
                    dist[vmask] = new_time;
                    pq.push({new_time, vmask});
                }
            }
        }
    };

    for(int riff = 0; riff < m; riff++) {
        vector<int64_t> dist(N, inf);
        for(int mask = 0; mask < N; mask++) {
            dist[mask] = prev_dp[mask];
        }
        run_dijkstra(dist);

        vector<int64_t> next_dp(N, inf);
        for(int mask = 1; mask < N; mask++) {
            if(dist[mask] < inf) {
                bool capsize = sum_w[mask] > c[riff];
                int raft_t = capsize ? D[riff] : d[riff];
                int seg_t = max(raft_t, max_out[mask]);
                next_dp[mask] = dist[mask] + seg_t;
            }
        }
        prev_dp = next_dp;
    }

    vector<int64_t> dist(N, inf);
    for(int mask = 0; mask < N; mask++) {
        dist[mask] = prev_dp[mask];
    }
    run_dijkstra(dist);

    cout << dist[0] << endl;
}

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 (detailed comments)

```python
import sys
import heapq

INF = 10**30

def solve() -> None:
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    m = int(next(it))

    # Participant parameters
    w = [0] * n  # weight
    t = [0] * n  # walking time per segment
    s = [0] * n  # swap time to get on/off raft
    for j in range(n):
        w[j] = int(next(it))
        t[j] = int(next(it))
        s[j] = int(next(it))

    # Riffle parameters
    c = [0] * m  # critical weight
    D = [0] * m  # time if capsizes
    d = [0] * m  # time if not
    for i in range(m):
        c[i] = int(next(it))
        D[i] = int(next(it))
        d[i] = int(next(it))

    N = 1 << n  # number of masks

    # Precompute mask properties
    sum_w = [0] * N
    max_out = [0] * N
    for mask in range(N):
        sw = 0
        mo = 0
        for j in range(n):
            if mask & (1 << j):
                sw += w[j]
            else:
                if t[j] > mo:
                    mo = t[j]
        sum_w[mask] = sw
        max_out[mask] = mo

    def run_dijkstra(dist):
        """
        Dijkstra on mask graph:
          node = mask (who is on raft)
          edge: mask -> mask^(1<<j) with cost s[j]
        dist[] is modified in place.
        """
        pq = []
        for mask in range(N):
            if dist[mask] < INF:
                heapq.heappush(pq, (dist[mask], mask))

        while pq:
            cur, umask = heapq.heappop(pq)
            if cur != dist[umask]:
                continue

            for j in range(n):
                vmask = umask ^ (1 << j)
                nd = cur + s[j]
                if nd < dist[vmask]:
                    dist[vmask] = nd
                    heapq.heappush(pq, (nd, vmask))

    # DP: prev[mask] best time at current point with this raft set
    prev = [INF] * N
    prev[0] = 0  # start: all on bank

    for i in range(m):
        # swaps at point p_i
        dist = prev[:]
        run_dijkstra(dist)

        # traverse riffle i with non-empty raft
        nxt = [INF] * N
        for mask in range(1, N):
            if dist[mask] >= INF:
                continue
            raft_time = D[i] if sum_w[mask] > c[i] else d[i]
            seg_time = raft_time if raft_time > max_out[mask] else max_out[mask]
            nxt[mask] = dist[mask] + seg_time

        prev = nxt

    # final swaps at finish to get mask=0
    dist = prev[:]
    run_dijkstra(dist)
    print(dist[0])


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