# Tima Goes to Xentopia

Image by WikiImages.

The city of Xentopia has a well-connected railway network. The city has *N* junctions
numbered from 1 to *N*. There are *M* pairs of railway tracks that exist
between the junctions. Trains can travel in both directions on each track. Each railway track
is labeled either red, blue, or white in color.

Tima, a tourist in the city, wants to travel from junction *S* to junction *T*
in the minimum possible time. She has a map of the railway network that she can use to
achieve this goal.

Tima, being rather eccentric, has an interesting constraint for her travel: she wants to
travel via exactly *k*_{1} red tracks, exactly *k*_{2} blue
tracks, and any number of white tracks, in any order. She is fine with using a railway track
more than once.

Can you tell the minimum time Tima will take to go from *S* to *T* ensuring
that her constraint is not violated?

## Input Specification

The first line contains four space-separated integers: *N*
(1 ≤ *N* ≤ 450), *M*
(1 ≤ *M* ≤ 1 100), *k*_{1}, and
*k*_{2}
(0 ≤ *k*_{1}, *k*_{2} ≤ 800,
*k*_{1} · *k*_{2} ≤ 800).
Following are *M* lines. Each line contains four space-separated integers
*U V X C*, denoting that a track exists between junction *U* and
junction *V*
(1 ≤ *U*, *V* ≤ *N*,
*U* ≠ *V*), the train covers this track in *X* seconds
(0 ≤ *X* ≤ 10^{9}), and the track is labeled
color *C* (0 ≤ *C* ≤ 2). A white track is
denoted by *C* = 0, a red track is denoted by *C* = 1, and
a blue track is denoted by *C* = 2.

The last line contains two space-separated integers *S*
(1 ≤ *S* ≤ *N*) and *T*
(1 ≤ *T* ≤ *N*), the source and destination of
Tima's journey, respectively. Note: *S* may be equal to *T*.

## Output Specification

Print a single integer denoting the total time Tima would take. If it is not possible for
Tima to reach her destination using exactly *k*_{1} red tracks,
*k*_{2} blue tracks, and any number of white tracks, output –1.

## Sample Input 1

`4 4 1 1`

`1 2 1 2`

`1 3 1 0`

`2 4 1 1`

`3 4 1 0`

`1 4`

download as text file
## Output for Sample Input 1

`2`

download as text file
## Sample Input 2

`4 3 200 1`

`1 2 1 1`

`2 3 1 0`

`2 4 1 2`

`1 3`

download as text file
## Output for Sample Input 2

`-1`

download as text file
## Original Problem

ICPC North Central North America Regional Programming
Contest, 2019