Maximize Charter Flight Profit

You are given K identical airplanes and N airports numbered from 0 to N-1, where airport 0 is the base. Each day, an airplane can start its operation from airport 0 at time 0 and must return to airport 0 no later than time T.

The airline receives M charter flight requests. Each request is described by five numbers: a departure time \(s\), a departure airport \(a\), an arrival time \(t\), an arrival airport \(b\), and a net profit \(c\). Fulfilling a request means that if at time \(s\) there is an airplane available at airport \(a\), you can assign that airplane to the request. The airplane will then arrive at airport \(b\) exactly at time \(t\) and you gain a profit of \(c\).

You are to design a schedule (assignment of airplanes to requests) so that each airplane’s schedule is feasible with respect to time and location, and every airplane starts at airport 0 at time 0 and must return to airport 0 by time \(T\). Note that if an airplane ends up at an airport other than 0 at time \(T\), it can perform a repositioning flight at time \(T\) (with no profit) to return to airport 0. Your task is to compute the maximum total profit that can be obtained.

Input and Output Note: All times are given in non‐negative integers. A request is only feasible if it fits within an airplane’s schedule. There is no extra repositioning allowed except at time \(T\) (from any airport to airport 0).

inputFormat

The first line contains four integers \(N\), \(M\), \(K\), and \(T\) (the number of airports, the number of requests, the number of airplanes, and the latest time by which each airplane must return to airport 0).

Each of the next \(M\) lines contains five integers: \(s\), \(a\), \(t\), \(b\), and \(c\), where a request means an airplane departs from airport \(a\) at time \(s\) and arrives at airport \(b\) at time \(t\) with a net profit of \(c\).

outputFormat

Print a single integer: the maximum total profit that can be obtained by scheduling the airplanes under the given constraints.

sample

1 0 1 10

0