სპილოები

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

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

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

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

წყარო: პოლონეთი, ოლიმპიადა 16, ეტაპი 1


ზოოპარკში იგეგმება ჩვენება, რომელშიც მონაწილეობას იღებს ყველა სპილო. ზოოპარკში მომუშავე ხალხმა უკვე განალაგა  სპილოები 1 ხაზად  ჩვენებისათვის, რადგან ზოოპარკის დირექტორის ბრძანებით ეს უნდა იყოს ჩვენების საწყისი ფიგურა.

            როდესაც დირექტორი მოვიდა საწყისი ფიგურის შესაფასებლად, მას სპილოების განლაგება არ მოეწონა და გასცა ბრძანება, რომ სპილოების წყობა შეეცვალათ ისე, როგორც მას უკეთესად მიაჩნდა.

            მომუშავეებმა დაიწყეს  სპილოების ახალი წყობით განლაგება, სპილოების წყვილებში გაცვლით.  ენერგია რაც თითო გაცვლას სჭირდება არის სპილოების მასების ჯამი, (მაგალითად პირველ და მესამე სპილოს ვუცვლით ადგილებს. პირველი სპილოს მასა m1-ია მეორესი m2 გაცვლის ენერგია  = m1+m2) ჩვენი მისიაა სასურველ ფიგურამდე მივიდეთ მინიმალური ენერგიის დახარჯვით.

უნდა დავწეროთ პროგრამა რომელიც:

            წაიკითხავს ზოოპარკში განლაგებული სპილოების წონებს, საწყის პოზიციებს და სამიზნე პოზიციებს. იპოვის გზას, მინიმალური ძალის(ენერგიის) გამოყენებით,  საწყისი პოზიციიდან სამიზნე პოზიციამდე მისასვლელად. სპილოები დანომრილია 1-დან n-ამდე.  გამოსატანი ველი ჯამური ენერგია, რომელიც ცვლილებებს მოხმარდა.

პირველ ხაზში შემოდის სპილოების რაოდენობა n( 2 <= n <= 1000 000) მეორე ხაზში შემოდის სპილოების წონები დაშორებული 1 სპეისით mi (100<= mi <=6500).  მესამე ხაზში შემოდის სპილოების საწყისი პოზიციები და ბოლო ხაზში შემოდის სპილოების სამიზნე პოზიციები (2<= Ci,Di<=n).




მაგალითები

შესატანი მონაცემები
6 2400 2000 1200 2400 1600 4000 1 4 5 3 6 2 5 3 2 4 6 1 დაკოპირება
გამოსატანი მონაცემები
11200 დაკოპირება

შენიშვნა

თავიდან 2-5 გაცვლიან ადგილებს, რაც მოითხოვს 2000 + 1600 =3600 ენერგიას

 და მივიღებთ 1 4 2 3 6 5 პოზიციას.

შემდეგ 3-4 გაცვლიან ადგილებს 1200+2400=3600 ენერგია -  1 3 2 4 6 5

და ბოლოს 1-5 გაცვლიან 2400 + 1600 = 4000 ენერგიის ხარჯზე და მივიღებთ- 5 3 2 4 6 1

ჯამში 4000+ 3600 + 3600 =  11200.