// Source: https://usaco.guide/general/io #include <bits/stdc++.h> using namespace std; using ll = long long; #define eb emplace_back // faster than push_back xD // pbds UwU #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define oset tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> // use pair for ms // my io library :D #define m1(x) template<class T, class... U> void x(T&& a, U&&... b) #define m2(x) (ll[]){(x forward<U>(b),0)...} m1(pr){cout << forward<T>(a); m2(cout << " " <<); cout << "\n";} m1(re){cin >> forward<T>(a); m2(cin >>);} const ll cap = 1e5+1; vector<pair<ll,ll>> adj[cap]; ll indegree[cap]; int main() { ios::sync_with_stdio(0); cin.tie(0); ll n, m, h; re(n, m, h); for (ll i{}; i < n-1; i++){ for (ll j{}; j < h; j++){ ll b, w; re(b, w); if (b > i) { adj[i].eb(make_pair(b,w)); indegree[b]++; } } } queue<ll> q; for (ll i{}; i <= n-1; i++){ if (indegree[i] == 0) q.push(i); } vector<ll> order; while (!q.empty()){ ll s = q.front(); q.pop(); order.eb(s); for (auto pr: adj[s]){ ll u = pr.first; indegree[u]--; if (indegree[u] == 0) q.push(u); } } vector<vector<ll>> dp(n, vector<ll>(m+1, 0)); dp[0][0] = 1; for (auto i: order){ for (auto pr: adj[i]){ ll v = pr.first, w = pr.second; for (ll k{}; k < m; k++){ for (ll t=w; k+t < m; t++){ dp[v][k+t] += dp[i][k]; if (dp[v][k+w] > (ll)5e8){ dp[v][k+w] = 5e8+1; } } } } } for (ll i{}; i < m; i++){ pr(dp[n-1][i]); } }