დროის ლიმიტი: 1 წმ
მეხსიერების ლიმიტი: 256 მეგაბაიტი
შემავალი მონაცემები: stdin
გამომავალი მონაცემები: stdout
წყარო: USACO, 2002/03, FALL, GREEN
ბესიმ მოიპარა ჰამბურგერები. ამიტომ დასჯის მიზნით ფერმერ ჯონმა მის გარშემო საპატიმროს დაშენება გადაწყვიტა. საპყრობილე უნდა აიგოს მონაკვეთების ფორმის კედლებისაგან რაოდენობით N (3 <= N <= 100). დამატებითი უსაფრთხოების მიზნით საპატიმროს ამოზნექილ მრავალკუთხედს უნდა წარმოადგენდეს, რომ ნებისმიერი მისი წერტილი გამოჩნდეს საპატიმროს სხვა ნებისმიერ წერტილიდან.
ჯონის პარტნიორმა შესთავაზა მას სია, სადაც მოყვანილია შესაძლო კედლების ფასები მათი განლაგების მიხედვით. ჯონს შეუძლია ააშენოს N კედელი და მან იცის მათი ბოლოების კოორდინატები და ფასები. ძროხა ბესსის და კედლების წვეროების კოორდინატები მთელი რიცხვებია დიაპაზონში -10000..10000. ძროხის განლაგება არ ემთთხვევა არც ერთ შესაძლო კედლის მონაკვეთს. დაადგინეთ ასარჩევი კედლების მინიმალურად შესაძლო საერთო ფასი ისე რომ კედლებმა შეადგინონ ამოზნექილი მრავალკუთხედი და ბესი აღმოჩნდეს შეპყრობილი.
შესატანი მონაცემები:
* სტრიქონი 1: შეიცავს ღარით გამოყოფილ სამ მთელს: N და ბესის კოორდინატებს X,Y.
* სტრიქონები 2..N+1: თითოეული შეიცავს ღარით გამოყოფილ 5 მთელ რიცხვს.
პირველი ორი წარმოადგენენ შესაძლო კედლის პირველი წვეროს კოორდინატებს, შედეგ კედლის მეორე წვეროს კოორდინატებს და ბოლოს კედლის ფასს C (1 <= C <= 10000) .
გამომავალი ფაილის ფორმატი:
ერთი სტრიქონი ერთი მთელი რიცხვით, რომელიც აღნიშნავს აშენებული კედლების მინიმალურ ფასს. თუ დასაშვები საპყრობილე ვერ აშენდება დაბეჭდეთ -1.
შესატანი მონაცემები
8 1 1 0 0 0 3 2 0 0 3 1 2 3 1 2 3 2 0 3 1 2 1 1 2 2 3 1 0 3 2 3 4 1 2 0 0 8 3 1 0 3 8 დაკოპირება
გამოსატანი მონაცემები
10 დაკოპირება
გამოყენებულია პირველი, მეორე, მესამე და მეექვსე კედლები.