განძის ძიება

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

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

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

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

წყარო: USACO, 2000/01, WINTER, GREEN


ფერმერმა ჯონმა (იგივე – ფჯ) იპოვა რუკა, რომელზეც აღნიშნულია მისი ფერმის ტერიტორიაზე ჩამარხული განძები. განძები ჩამოთვლილია მიმდევრობით 1..N (1≤N≤80). ყოველი განძი ჩამარხულია განსხვავებული მთელი (x,y) კოორდინატის მქონე ადგილზე და ჩამარხვის სიღრმე მოცემულია ასევე მთელი z რიცხვით, ხოლო განძის ღირებულება ასევე მთელი V მნიშვნელობით.

ფჯ ნებისმიერ ორ პუნქტს შორის მოძრაობს ე.წ. “მანჰეტენის” სტილით, რაც გამორიცხავს დიაგონალურ მოძრაობას. მაგალითად (1,2) კოორდინატების მქონე პუნქტიდან (5,7) კოორდინატების მქონე პუნქტამდე ფჯ-მ უნდა გაიაროს მანძილის ოთხი ერთეული პირველი კოორდინატის გასწვრივ და შემდეგ 5 ერთეული მეორე კოორდინატის გასწვრივ. მანძილის თითო ერთეულის გავლას ფჯ ანდომებს ერთ წუთს და ასევე ერთ წუთს ხარჯავს 0,5 ერთეულის ამოთხრაზე. თქვენ აგრეთვე გეძლევათ მთელი რიცხვით აღწერილი T დრო, რომელიც შეუძლია გამოიყენოს ფჯ-ს განძის ძიებაზე მთლიანად.

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

შემავალი მონაცემები: პირველ სტრიქონში მოცემულია ორი მთელი რიცხვი: N (1≤N≤80)-და T (1≤T≤1000000). 2-დან N+1 სტრიქონამდე თითოეულში მოცემულია ჰარით გამოყოფილი ოთხი მთელი რიცხვი, რომლებიც აღწერენ შესაბამის განძს: x (-100≤x≤100), y (-80≤y≤80), z (0<z≤25) და V (1≤V≤1000).

გამომავალი მონაცემები: ერთადერთი სტრიქონი ერთადერთი მთელი რიცხვით, რომელიც წარმოადგენს ფჯ-ს მიერ მოპოვებული მაქსიმალური ღირებულების განძს მოცემულ დროში. 




მაგალითები

შესატანი მონაცემები
3 20 2 3 2 5 -5 0 8 51 2 -2 1 14 დაკოპირება
გამოსატანი მონაცემები
19 დაკოპირება