#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef unsigned long long int ulint; typedef long long int llint; typedef long double lldo; #define mp make_pair #define mt make_tuple #define pub push_back #define puf push_front #define pob pop_back #define pof pop_front #define fir first #define sec second #define res resize #define ins insert #define era erase #define RE return 0 //ios::sync_with_stdio(false); //std::cin.tie(0); //<< setprecision(20) const int mod=(int)1e9+7; const llint big=(llint)(2.19e15+1); const long double pai=3.141592653589793238462643383279502884197; const long double ena=2.71828182845904523536; const long double eps=1e-7; template bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;} template bool maxeq(T& a,U b){if(a void soun(T& ar) {sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());} llint gcd(llint a,llint b){if(a%b==0){return b;}else{return gcd(b,a%b);}} llint lcm(llint a,llint b){return a/gcd(a,b) *b;} template auto LB(T& ve,U in){return lower_bound(ve.begin(),ve.end(),in);} template auto UB(T& ve,U in){return upper_bound(ve.begin(),ve.end(),in);} template auto LBI(T& ve,U in){return LB(ve,in)-ve.begin();} template auto UBI(T& ve,U in){return UB(ve,in)-ve.begin();} template void SO(T& ve){sort(ve.begin(),ve.end());} template void REV(T& ve){reverse(ve.begin(),ve.end());} class dinic{ public: int n,sta,gol; vector> hen; vectordis;//bfsの距離 //隣接行列(O(VVE)なので) vector>tna; //hen[town][i]>0 を探す dinic(int in,int s,int g){ n=in; sta=s; gol=g; hen.res(in); dis.res(in); tna.res(in); for(int i=0;i>que; que.push(mp(0,sta)); dis[sta]=0; while(!que.empty()){ int kyo=que.front().fir; int town=que.front().sec; que.pop(); for(auto i:tna[town]){ if(hen[town][i]!=0&&dis[i]==-1){dis[i]=kyo+1;que.push(mp(kyo+1,i));} } } } llint dfs(int ter,llint lim){ //それまでの上限がlim //流した量を返す if(ter==gol){return lim;} llint ans=0; for(auto i:tna[ter]){ if(dis[ter]>=dis[i]||hen[ter][i]==0){continue;}//dinic if(lim==ans){break;} llint nga=dfs(i,min(lim-ans,hen[ter][i])); ans+=nga; hen[ter][i]-=nga; hen[i][ter]+=nga; tna[i].ins(ter); } return ans; } llint solve(void){ llint ans=0; while(-1){ bfs(); llint nga=dfs(sta,big); ans+=nga; if(nga==0){break;} } return ans; } }; int main(void){ //♨♨フロー♨♨ //はいフロー 貼るだけ界のtourist llint n,m,d,i,j;cin>>n>>m>>d; dinic gra(m+m,0,0); vector>> zyu(n); for(i=0;i>u>>v>>p>>q>>w;u--;v--;q+=d; gra.add(i+m,i,w); zyu[u].pub(mp(p,i+m)); zyu[v].pub(mp(q,i)); } for(i=0;i