Hongik University Underground Campus

Hongik University's Seoul campus buildings are connected from the front gate to the back gate, but the floors that connect them differ from building to building. For example, leaving building R on its 3rd floor leads to the 1st floor of building K, and leaving building L on its 8th floor leads to the 1st floor of building I. The campus is small but tangled, so students call it 'Hogwarts'.

Architecture student Gyeolyeol needs to design an underground campus that connects the front gate to the back gate and shows these features, and submit it as an assignment. Gyeolyeol thinks there is far too little time to finish it alone and is about to give up. Let's help Gyeolyeol.

For Gyeolyeol, we took M models from a well-known building model site. Each model can be printed directly on a 3D printer, and the assignment is complete by joining the models together. Every model can also be flipped left to right. (A model cannot be flipped upside down.)

• Because of the assignment's rules, buildings can only be placed from B1 to BN.
• Every building has one entrance on each side, and when two buildings connect, their entrances must meet, as in the figure.
• Each model has a floor count H_i, and entrance floors E_i1 and E_i2. Printing a model takes time T_i.
• The same model can be used more than once, and each use takes the same time.
• The front gate has an entrance on floor R, and the back gate has an entrance on floor D. These are the start and end points of the underground campus.

The height of the models cannot be changed, but changing their width is easy. So the number of buildings used does not matter. Find the minimum time needed to design the campus and tell Gyeolyeol.

Given the three models above, the values of H, T, E1, and E2 are the numbers in the boxes below each model.

With N = 9, R = 3, and D = 2, the design that gives the minimum time using these three models is shown below.

The time for this design is 38.

The first line contains N, the number of underground floors where buildings can be placed (2 ≤ N ≤ 2,000).

The second line contains R and D, the floors of the front gate and back gate entrances (1 ≤ R ≤ N, 1 ≤ D ≤ N).

The third line contains M, the number of models (1 ≤ M ≤ 2,000).

Each of the next M lines contains H_i, T_i, E_i1, and E_i2, separated by spaces: the number of floors of the model, the printing time T_i (1 ≤ T_i ≤ 1,000,000), and the two entrance floors. (2 ≤ H_i ≤ N, 1 ≤ E_i1 ≤ H_i, 1 ≤ E_i2 ≤ H_i, and E_i1 ≠ E_i2.)

Print the minimum time needed to finish the assignment.

If the campus cannot be designed with the given models, print -1.