## 1. Abridged Problem Statement

A group of M tourists must cross a river of width W by jumping among N floating rubbish piles at coordinates (xi, yi). Each jump (in any direction) can cover at most distance D and takes exactly 1 second. Pile i can hold at most ci tourists simultaneously. Tourists start on the near bank (y=0) and wish to reach the far bank (y=W). Determine the minimal time for all M tourists to cross, or report IMPOSSIBLE.

---

## 2. Detailed Editorial

We model the crossing as a maximum-flow problem on a time-expanded network.

### Time-expanded graph

For each time step t and each pile i we create two nodes: an "in" node and an "out" node. The pile capacity is enforced by an edge in(t,i) -> out(t,i) of capacity ci.

- Source and sink: a super-source S and super-sink T.
- Edges from the start bank: at every time t, if pile i is within jump distance D of y=0 (i.e., yi <= D), add an infinite-capacity edge S -> in(t,i).
- Edges to the far bank: at every time t, if yi + D >= W, add an infinite-capacity edge out(t,i) -> T.
- Jump edges between piles: for each t > 0, and for any two piles i and j with squared distance <= D^2, add an infinite-capacity edge out(t-1,j) -> in(t,i).
- Special case: if D >= W, every tourist can jump directly from bank to bank in 1 second; answer is 1.

### Incremental layer approach

Rather than binary-searching over the number of time layers, we build the full graph upfront (up to max_ans = N + 1 + M layers) and add one time layer at a time. After adding each new layer t, we call the max-flow algorithm incrementally. Because Dinic's algorithm preserves the residual graph state between calls, the new layer's edges can route additional flow using paths that were previously blocked by capacity limits.

The first time t at which the cumulative flow reaches M tourists is the answer: every tourist can have crossed, taking t + 2 seconds (one step onto the first pile, t inter-pile jumps, one step to the far bank). If all max_ans layers are exhausted without reaching M, output IMPOSSIBLE.

This incremental approach avoids rebuilding the full graph for each candidate T, saving work compared to binary search.

### Complexity

N <= 50, M <= 50, T <= N + M + 1 <= 101. Dinic's algorithm handles these sizes easily in time.

---

## 3. C++ Solution

```cpp
#include <bits/stdc++.h>
// #include <coding_library/graph/maxflow.hpp>

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

template<class T>
class MaxFlow {
  private:
    struct Edge {
        T flow, cap;
        int idx, rev, to;
        Edge(int _to, int _rev, T _flow, T _cap, int _idx)
            : to(_to), rev(_rev), flow(_flow), cap(_cap), idx(_idx) {}
    };

    vector<int> dist, po;
    int n;

    bool bfs(int s, int t) {
        fill(dist.begin(), dist.end(), -1);
        fill(po.begin(), po.end(), 0);

        queue<int> q;
        q.push(s);
        dist[s] = 0;

        while(!q.empty()) {
            int u = q.front();
            q.pop();

            for(Edge e: adj[u]) {
                if(dist[e.to] == -1 && e.flow < e.cap) {
                    dist[e.to] = dist[u] + 1;
                    q.push(e.to);
                }
            }
        }
        return dist[t] != -1;
    }

    T dfs(int u, int t, T fl = INF) {
        if(u == t) {
            return fl;
        }

        for(; po[u] < (int)adj[u].size(); po[u]++) {
            auto& e = adj[u][po[u]];
            if(dist[e.to] == dist[u] + 1 && e.flow < e.cap) {
                T f = dfs(e.to, t, min(fl, e.cap - e.flow));
                e.flow += f;
                adj[e.to][e.rev].flow -= f;
                if(f > 0) {
                    return f;
                }
            }
        }

        return 0;
    }

  public:
    const static T INF = numeric_limits<T>::max();

    MaxFlow(int n = 0) { init(n); }

    vector<vector<Edge>> adj;

    void init(int _n) {
        n = _n;
        adj.assign(n + 1, {});
        dist.resize(n + 1);
        po.resize(n + 1);
    }

    void add_edge(int u, int v, T w, int idx = -1) {
        adj[u].push_back(Edge(v, adj[v].size(), 0, w, idx));
        adj[v].push_back(Edge(u, adj[u].size() - 1, 0, 0, -1));
    }

    T flow(int s, int t) {
        assert(s != t);

        T ret = 0, to_add;
        while(bfs(s, t)) {
            while((to_add = dfs(s, t))) {
                ret += to_add;
            }
        }

        return ret;
    }
};

int n, m, jump_d, w;
vector<tuple<int, int, int>> rubish;

void read() {
    cin >> n >> m >> jump_d >> w;
    rubish.resize(n);
    for(auto& [x, y, z]: rubish) {
        cin >> x >> y >> z;
    }
}

void solve() {
    // Tourists hop between piles at one jump per second, each pile holding at
    // most its capacity at any single instant, so this is a flow over a
    // time-expanded graph. For each time step t and pile i we keep an in-node
    // and an out-node joined by an edge of capacity c (the pile's capacity at
    // that instant). The super source feeds the in-node of every pile reachable
    // from the start bank (y <= jump_d), and the out-node of every pile that
    // can reach the far bank (y + jump_d >= w) feeds the super sink, both with
    // infinite capacity. Between consecutive layers an infinite edge links the
    // out-node of pile j at time t-1 to the in-node of pile i at time t whenever
    // the squared distance between them is within jump_d^2, modelling a jump.
    //
    // We add one time layer at a time and accumulate the extra max flow source
    // -> sink it unlocks. The first time t at which the cumulative flow reaches
    // m tourists, every tourist can have crossed, taking t + 2 seconds (one
    // step onto the first pile, t inter-pile jumps, one step to the far bank).
    // If jump_d already spans the river the answer is 1; if max_ans layers are
    // exhausted without reaching m it is impossible.

    if(jump_d >= w) {
        cout << 1 << '\n';
        return;
    }

    int max_ans = n + 1 + m;
    int num_vers = 2 + max_ans * 2 * n;
    int source = num_vers - 2, sink = num_vers - 1;

    auto encode_state = [&](int t, int i, int in_out_flag) {
        return t * 2 * n + 2 * i + in_out_flag;
    };

    MaxFlow<int> mf(num_vers);

    int flow = 0;
    for(int t = 0; t < max_ans; t++) {
        for(int i = 0; i < n; i++) {
            auto [x, y, c] = rubish[i];
            if(y <= jump_d) {
                mf.add_edge(source, encode_state(t, i, 0), MaxFlow<int>::INF);
            }
            mf.add_edge(encode_state(t, i, 0), encode_state(t, i, 1), c);
            if(y + jump_d >= w) {
                mf.add_edge(encode_state(t, i, 1), sink, MaxFlow<int>::INF);
            }

            if(t > 0) {
                for(int j = 0; j < n; j++) {
                    auto [x2, y2, _] = rubish[j];
                    if((x - x2) * (int64_t)(x - x2) +
                           (y - y2) * (int64_t)(y - y2) <=
                       jump_d * (int64_t)jump_d) {
                        mf.add_edge(
                            encode_state(t - 1, j, 1), encode_state(t, i, 0),
                            MaxFlow<int>::INF
                        );
                    }
                }
            }
        }

        flow += mf.flow(source, sink);
        if(flow >= m) {
            cout << t + 2 << '\n';
            return;
        }
    }

    cout << "IMPOSSIBLE\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();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 4. Python Solution with Comments

```python
import sys
from collections import deque

class Dinic:
    def __init__(self, n):
        self.n = n
        self.adj = [[] for _ in range(n)]
        self.level = [0]*n
        self.it = [0]*n

    def add_edge(self, u, v, c):
        # forward edge index len(adj[u]), backward edge index len(adj[v])
        self.adj[u].append([v, c, len(self.adj[v])])
        self.adj[v].append([u, 0, len(self.adj[u]) - 1])

    def bfs(self, S, T):
        for i in range(self.n):
            self.level[i] = -1
        dq = deque([S])
        self.level[S] = 0
        while dq:
            u = dq.popleft()
            for v, cap, rev in self.adj[u]:
                if cap > 0 and self.level[v] < 0:
                    self.level[v] = self.level[u] + 1
                    dq.append(v)
        return self.level[T] >= 0

    def dfs(self, u, T, flow):
        if u == T:
            return flow
        for i in range(self.it[u], len(self.adj[u])):
            self.it[u] = i
            v, cap, rev = self.adj[u][i]
            if cap and self.level[v] == self.level[u] + 1:
                pushed = self.dfs(v, T, min(flow, cap))
                if pushed:
                    # reduce forward, increase backward
                    self.adj[u][i][1] -= pushed
                    self.adj[v][rev][1] += pushed
                    return pushed
        return 0

    def maxflow(self, S, T):
        flow = 0
        INF = 10**18
        while self.bfs(S, T):
            self.it = [0]*self.n
            while True:
                pushed = self.dfs(S, T, INF)
                if not pushed:
                    break
                flow += pushed
        return flow

def solve():
    data = sys.stdin.read().split()
    it = iter(data)
    N = int(next(it))
    M = int(next(it))
    D = int(next(it))
    W = int(next(it))
    piles = []
    for _ in range(N):
        x = int(next(it)); y = int(next(it)); c = int(next(it))
        piles.append((x, y, c))

    # Special case: direct jump bank->bank
    if D >= W:
        print(1)
        return

    # Precompute adjacency by distance
    adj = [[False]*N for _ in range(N)]
    for i in range(N):
        x1,y1,_ = piles[i]
        for j in range(N):
            x2,y2,_ = piles[j]
            dx, dy = x1-x2, y1-y2
            adj[i][j] = (dx*dx + dy*dy <= D*D)

    # Build full graph upfront and add one time layer at a time.
    # The Dinic residual graph is preserved between calls.
    max_ans = N + 1 + M
    node_cnt = 2 + max_ans * N * 2
    SRC, SNK = node_cnt - 2, node_cnt - 1
    dinic = Dinic(node_cnt)

    def in_id(t, i):
        return t * N * 2 + 2 * i
    def out_id(t, i):
        return t * N * 2 + 2 * i + 1

    cumulative_flow = 0
    for t in range(max_ans):
        # Add layer t's edges
        for i, (x, y, c) in enumerate(piles):
            # capacity of pile
            dinic.add_edge(in_id(t, i), out_id(t, i), c)
            # reachable from start bank
            if y <= D:
                dinic.add_edge(SRC, in_id(t, i), 10**18)
            # can jump to far bank
            if y + D >= W:
                dinic.add_edge(out_id(t, i), SNK, 10**18)
            # transitions from previous time
            if t > 0:
                for j in range(N):
                    if adj[j][i]:
                        dinic.add_edge(out_id(t-1, j), in_id(t, i), 10**18)

        # Accumulate incremental flow unlocked by this new layer
        cumulative_flow += dinic.maxflow(SRC, SNK)
        if cumulative_flow >= M:
            print(t + 2)
            return

    print("IMPOSSIBLE")

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

---

## 5. Compressed Editorial

Model the tourists' crossing as flow on a time-expanded graph: for each time step t and each pile i, create an "in" -> "out" edge of capacity ci. Connect the source to piles reachable from the start bank at every t, and piles able to reach the far bank to the sink. Between time layers add infinite-capacity edges for feasible jumps.

Build the full graph upfront and add one time layer at a time, calling max-flow after each new layer. The residual graph is preserved between calls so incremental flow can use capacity freed by earlier paths. The first time t at which the cumulative flow reaches M gives the answer as t + 2 seconds (or 1 if D >= W).
