SAMPLE INPUT
=====================================================================
9
18
1 2 0200 0400 AI1204 6000
1 4 0100 0200 AI3304 2000
4 3 0300 0500 AI3322 3000
2 7 0500 0700 AI8900 5000
7 5 0800 1000 AI8999 3000
3 6 0700 0900 AI5000 4000
6 5 1000 1300 AI3098 2000
5 4 1400 1500 AI8956 3000
1 6 0700 0900 AI6666 25000
4 3 1600 1800 AI3324 3000
6 7 0915 1100 AI4577 4500
5 7 1400 1600 AI6594 3500
1 8 0300 0400 AI8967 6500
1 9 0400 0600 AI2998 3500
5 8 0200 0600 AI4500 2800
7 9 0300 0700 AI3409 3900
2 8 2000 2100 AI8676 4800
8 3 2145 2245 AI6788 6700
9
1 5 0000 1400
1 5 0000 1100
1 3 0600 2000
3 7 0600 1200
1 5 0200 1400
3 7 0600 1500
3 7 0600 1630
2 3 1900 2300
8 9 2130 2330
=====================================================================
OUTPUT (ouput -1 if there is no flight satisfying the constraints)
=====================================================================
11000
14000
33000
-1
14000
-1
9500
11500
-1
=====================================================================