대피

$T$분 후 로키가 이끄는 치타우리 군대가 지구를 공격한다. 복수자들은 뉴욕에 포털이 열리는 것을 제때 막지 못했다. 그래서 캡틴 아메리카는 도시의 모든 주민을 대피시키기로 결정했다. 침공이 시작되기 전에 주민들이 도시를 빠져나갈 수 있는지 알아내야 한다.

뉴욕 주변은 일방통행 도로로 연결된 작은 도시들의 집합으로 볼 수 있다. 각 도로에는 길이와 통행 용량이 있다. 길이 $l$은 시각 $t$에 도로에 들어선 차가 시각 $t+l$에 도로 끝에 도착한다는 뜻이다. 통행 용량 $s$는 매분 이 도로에 들어설 수 있는 차량이 최대 $s$대라는 뜻이다. 차는 도시에 도착한 뒤 곧바로 그 도시에서 나가는 도로 중 하나로 이어 갈 수 있고, 원하는 만큼 그 도시에 머문 뒤에 떠날 수도 있다.

캡틴 아메리카는 대피한 주민이 모일 도시를 이미 정했다. 도시 전체를 대피시키는 데 필요한 차량 수도 알고 있다. 주민이 모두 침공 전에 대피할 수 있는지 판단해야 한다. 가능하다면 필요한 최소 시간을, 불가능하다면 안전한 도시에 제때 도착하지 못하는 차량 수의 최솟값을 구해야 한다.

첫 줄에 정수 $n$, $m$, $K$, $T$가 주어진다($1 \le n \times T \le 10\,000$, $1 \le m, K \le 10\,000$). 각각 주변 도시의 수, 도로의 수, 뉴욕에서 안전한 도시까지 가야 하는 차량의 수, 침공까지 남은 시간이다. 이어서 $m$개의 줄에 도로 정보가 주어진다.

각 도로는 정수 네 개 $u$, $v$, $l$, $s$로 주어진다($1 \le u, v \le n$, $u \ne v$, $1 \le s \le 3\,000$, $1 \le l \le 200$). 각각 출발 도시, 도착 도시, 길이, 통행 용량이다.

두 도시 사이에는 한 방향으로만 가는 도로가 최대 하나 있다. 뉴욕은 1번 도시이고, 안전한 도시는 $n$번 도시다. 시각 0에 모든 차량은 뉴욕에 있다.

모든 주민이 $T$분 이내에 안전한 도시에 도착할 수 있으면, 그들에게 필요한 최소 시간(분)을 출력한다. 그렇지 않으면 $T$분 안에 안전한 도시에 도착하지 못하는 차량 수의 최솟값을 출력한다. 어느 경우인지는 따로 적지 않아도 된다.