საპყრობილე ბესისათვის

დროის ლიმიტი: 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 დაკოპირება

შენიშვნა

გამოყენებულია პირველი, მეორე, მესამე და მეექვსე კედლები.