დენის გათიშვა

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: USACO, 2008/09, OCT


გრიგალმა ფერმერ ჯონს ელექტროგადამცემი ხაზებიდან ზოგიერთი  დაუზიანა. 
მას აქვს ყველა N (2 <= N <= 1,000) ბოძის რუკა, რომლებიც გადანომრილია 1-დან
N-მდე და განთავსებულნი არიან საკოორდინატო სიბრტყის
x_i,y_i (-100,000 <= x_i <= 100000;-100,000 <= y_i <= 100,000) წერტილებში. Pi და Pj (1 <= Pi <= N; 1 <= Pj <= N) ბოძების წყვილებს აერთებს W (1 <= W <= 10,000) სადენი. ფჯ-ს სურს 1-ლი ბოძიდან ელექტროენერგია N-ურ ბოძამდე მიიყვანოს, ამასთან საჭიროების შემთხვევაში საშუალედო ბოძებიც გამოიყენოს. გეძლევათ N ბოძის ადგილმდებარეობა და დაუზიანებელი ელექტროხაზების
სია. გაარკვიეთ ელექტროსადენის მინიმალური სიგრძე, რომელიც საჭიროა 1-ლი
ბოძიდან N-ურ ბოძამდე ელექტროგადაცემის აღსადგენად. არცერთი ელექტროსადენი
არ შეიძლება იყოს მოცემულ ნამდვილ M (0.0 < M <= 200,000.0) რიცხვზე მეტი. მაგალითისათვის ქვემოთ წარმოდგენილია 9 ბოძისა და 3 სადენის შემცველი რუკა
გრიგალის შემდეგ. ამასთან, M = 2.0. ოპტიმალური ამოხსნაა - შევაერთოთ ბოძები 4 და 6,
შემდეგ - 6 და 9. გრიგალის შემდეგ ოპტიმალური აღდგენა 3 . . . 7 9 . . . . . 3 . . . 7 9 . . . . . / 2 . . 5 6 . . . . . . 2 . . 5 6 . . . . . . / 1 2-3-4 . 8 . . . . . 1 2-3-4 . 8 . . . . . | | 0 1 . . . . . . . . . 0 1 . . . . . . . . . 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 ჯამური სიგრძე 1.414213562 + 1.414213562 = 2.828427124 . შეტანის ფორმატი: * სტრიქონი 1: ჰარით გაყოფილი ორი მთელი რიცხვი: N და W * სტრიქონი 2: ერთი ნამდვილი რიცხვი: M * სტრიქონები 3..N+2: ჰარით გაყოფილი ორი მთელი რიცხვი: x_i y_i * სტრიქონები N+3..N+2+W:ჰარით გაყოფილი ორი მთელი რიცხვი: Pi Pj გამოტანის ფორმატი: * სტრიქონი 1: ერთი მთელი რიცხვი. თუ აღდგენა შეუძლებელია, გამოიტანეთ -1. სხვა შემთხვევაში გამოიტანეთ ერთი მთელი რიცხვი, რომელიც 1000-ჯერ მეტია ელექტრომომარაგების აღდგენის მინიმალურ ღირებულებაზე. არანაირი დამრგვალება საჭირო არაა, უბრალოდ უგულებელჰყავით ამ ნამრავლის წილადი ნაწილი.



მაგალითები

შესატანი მონაცემები
9 3 2.0 0 0 0 1 1 1 2 1 2 2 3 2 3 3 4 1 4 3 1 2 2 3 3 4 დაკოპირება
გამოსატანი მონაცემები
2828 დაკოპირება

შენიშვნა

შეტანის განმარტება:
როგორც დიაგრამაზეა ნაჩვენები