Evacuation

In $T$ minutes, the Chitauri army led by Loki attacks Earth. The Avengers cannot stop the portal from opening in New York in time, so Captain America has decided to evacuate all of the city's residents. He needs to find out whether the residents can leave the city before the invasion begins.

The area around New York can be viewed as a set of small cities connected by one-way roads. Each road has a length and a capacity. A length $l$ means that a car entering the road at time $t$ reaches its far end at time $t+l$. A capacity $s$ means that at most $s$ cars can enter the road in any given minute. When a car reaches a city, it can immediately continue onto any road leaving that city, or it can stay in the city for any number of minutes before leaving.

Captain America has already chosen the city where New York's residents must be after the evacuation. He also knows how many cars are needed to evacuate the entire city. Now he must determine whether all residents can evacuate before the invaders arrive. If they can, find the minimum time they need. If they cannot, find the minimum number of cars carrying residents that will not reach the safe city.

The first line contains four integers $n$, $m$, $K$, and $T$ ($1 \le n \times T \le 10\,000$, $1 \le m, K \le 10\,000$): the number of cities around New York, the number of roads between them, the number of cars that must travel from New York to the safe city, and the time until the invasion. The next $m$ lines describe the roads.

Each road is described by four integers $u$, $v$, $l$, and $s$ ($1 \le u, v \le n$, $u \ne v$, $1 \le s \le 3\,000$, $1 \le l \le 200$): the city the road leaves from, the city it leads to, its length, and its capacity.

There is at most one road between any two cities, and it goes in one direction only. New York is city 1, and the safe city is city $n$. At time 0, all cars are in New York.

If all residents can reach the safe city in no more than $T$ minutes, print the minimum number of minutes they need. Otherwise, print the minimum number of cars that cannot reach the safe city within $T$ minutes. You do not need to say which case applies.