Bò muốn gần bạn khi xếp ăn. John có $N$ ($2\le N\le1{,}000$), số $1..N$, trên đường thẳng theo số. Chen lấn nên nhiều con có thể cùng vị trí tọa độ.

Bạn muốn giới hạn trên khoảng cách, ghét muốn dưới. $ML$ ($1\le ML\le10{,}000$) ràng buộc bạn cho tối đa, sau $MD$ ($1\le MD\le10{,}000$) ghét cho tối thiểu.

Tìm nếu được khoảng cách lớn nhất 1 với $N$ thỏa ràng buộc.

Dữ liệu vào

Dòng 1: nguyên $N,ML,MD$ cách trắng.

Dòng $2..ML+1$: dương $A,B,D$ cách trắng, $1\le A<B\le N$, khoảng cách tối đa $D$, $1\le D\le1{,}000{,}000$.

Dòng $ML+2..ML+MD+1$: dương $A,B,D$ cách trắng, $1\le A<B\le N$, khoảng cách ít nhất $D$, $1\le D\le1{,}000{,}000$.

Dữ liệu ra

Dòng 1: nguyên, không được $-1$, 1 và $N$ xa tùy ý $-2$, còn lại lớn nhất.

Ví dụ

Dữ liệu vào 1

4 2 1
1 3 10
2 4 20
2 3 3

Dữ liệu ra 1

27

Ghi chú

Ghi chú

Giải thích ví dụ:

4 bò, 1 và3 tối đa10, 2 và4 tối đa20, ghét2 và3 tối thiểu3.

Tọa độ tốt nhất: 1 tại0, 2 tại7, 3 tại10, 4 tại27.