الأبقار تحب قرب الأصدقاء بصف الطعام. John لديه $N$ ($2\le N\le1{,}000$)، أرقام $1..N$، على خط بترتيب الأرقام. قد تتدافع فتشترك عدة أبقار بنفس الموضع والإحداثي.

الأصدقاء يريدون حدًا أقصى للمسافة، الأعداء أدنى. $ML$ ($1\le ML\le10{,}000$) قيود أصدقاء تعطي الأقصى، ثم $MD$ ($1\le MD\le10{,}000$) أعداء تعطي الأدنى.

احسب إن أمكن أكبر مسافة بين 1 و$N$ تحقق القيود.

الإدخال

السطر 1: صحيحة $N,ML,MD$ بفراغات.

الأسطر $2..ML+1$: موجبة $A,B,D$ بفراغات، $1\le A<B\le N$، مسافة لا تزيد عن $D$، $1\le D\le1{,}000{,}000$.

الأسطر $ML+2..ML+MD+1$: موجبة $A,B,D$ بفراغات، $1\le A<B\le N$، مسافة لا تقل عن $D$، $1\le D\le1{,}000{,}000$.

الإخراج

السطر 1: صحيح، مستحيل $-1$، 1 و$N$ بلا حد للمسافة $-2$، وإلا أكبر مسافة.

أمثلة

الإدخال 1

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

الإخراج 1

27

ملاحظة

ملاحظة

شرح المثال:

4 أبقار، 1 و3 أقصى 10، 2 و4 أقصى 20، الأعداء 2 و3 أدنى 3.

أفضل إحداثيات: 1 عند 0، 2 عند 7، 3 عند 10، 4 عند 27.