ДАРХАНЫ 26-р ДУНД СУРГУУЛЬ / 9-р анги /

Нэгэн зорчигч бүс нутгийн тосгодоор аялж байв. Зорчигчид их биш учраас автобус өдөртөө цөөхөн явж байв.

Тэрээр d тосгоноос v тосгонд хурдхан хүрмээр байна. ( d тосгонд байх хугацааг 0 гэж тооцно.)

Input

Эхний мөрөнд тосгодын тоо N ( 1<=N<=100 ). Хоёр дахь мөрөнд d, v тосгодын дугаар.

Дараагийн мөрөнд автобусны рейсийн тоо R өгөгөдөнө. ( 0<=R<=10000).

Дараагийн R мөрүүдэд автобусны рейсүүд өгөдөнө. Рейс бүр нь автобус гарах тосгоны дугаар, автобус хөдлөх цаг, хүрэх тосгоны дугаар, хүрэлцэн очих хугацаа 4-өөр тус тус өгөгдөнө. ( Бүх хугацаанууд [0; 10000] завсрын бүхэл тоо байна.)

Зорчигч ятар нэг тосгонд  t агшинд хүрэлцэн очсон бол яг тэр t агшинаас эхлэн рейсийн хуваарийн дагуу дараагийн тосгон руу хөдөлсөн гэж тооцно.

Output

Зорчигчийн v тосгонд хүрч очих хамгийн бага хугацаа. Автобусны рейсүүд ашиглан d тосгоноос v тосгонд хүрэх боломжгүй бол -1.

Example

Input:
3

1 3

4

1 0 2 5

1 1 2 3

2 3 3 5

1 1 3 10
Output:
5