#include using namespace std; typedef long long ll; #define i_7 (ll)(1E9+7) #define i_5 (ll)(1E9+5) ll mod(ll a){ ll c=a%i_7; if(c>=0)return c; else return c+i_7; } typedef pair i_i; typedef pair l_l; //ll inf=(ll)1E12; #define rep(i,l,r) for(ll i=l;i<=r;i++) #define pb push_back ll max(ll a,ll b){if(ab)return b;else return a;} void Max(ll * pos,ll val){*pos=max(*pos,val);}//Max(&dp[i][j],dp[i-1][j]); void Min(ll * pos,ll val){*pos=min(*pos,val);} void Add(ll * pos,ll val){*pos=mod(*pos+val);} const long double EPS=1E-8; //////////////////////////////////////// int inf=(int)1E9+5; #define MAX_V 30000//調節!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! //辺を表す構造体{行き先、容量、逆辺} struct edge{ll to,cap,rev;}; vector G[MAX_V]; bool used[MAX_V];//dfsですでに調べたかのフラグ //fromからtoへの流量capの辺をグラフに追加 void add_edge(ll from,ll to,ll cap){ G[from].push_back((edge){to,cap,static_cast(G[to].size())}); G[to].push_back((edge){from,0,static_cast(G[from].size()-1)}); } //増加パスをdfsで探す ll dfs(ll v,ll t,ll f){ if(v==t)return f; used[v]=true; for(ll i=0;i0){ ll d=dfs(e.to,t,min(f,e.cap)); if(d>0){ e.cap-=d; G[e.to][e.rev].cap+=d; return d; } } } return 0; } ll max_flow(ll s,ll t){ ll flow=0; while(1){ memset(used,0,sizeof(used)); ll f=dfs(s,t,inf); if(f==0)return flow; flow+=f; } } /////////////////////////////////////// ll num(vectorv,ll val){ return lower_bound(v.begin(),v.end(),val)-v.begin(); } struct plane{ ll u,v,p,q,w; }; int main(){ ll n,m,d;cin>>n>>m>>d; vectorpla; vectortime[n]; rep(i,0,m-1){ plane aa; cin>>aa.u>>aa.v>>aa.p>>aa.q>>aa.w;aa.u--;aa.v--; aa.q+=d; time[aa.u].pb(aa.p); time[aa.v].pb(aa.q); pla.pb(aa); } rep(i,0,n-1){ sort(time[i].begin(),time[i].end()); time[i].erase(unique(time[i].begin(),time[i].end()),time[i].end()); } ll start[n+1]; start[0]=0; rep(i,1,n){ start[i]=start[i-1]+time[i-1].size(); } for(plane pp:pla){ ll s=start[pp.u]+num(time[pp.u],pp.p); ll t=start[pp.v]+num(time[pp.v],pp.q); add_edge(s,t,pp.w); } rep(i,0,n-1){ if(time[i].size()<=1)continue; rep(j,0,time[i].size()-2){ add_edge(start[i]+j,start[i]+j+1,inf); } } cout<