სამეცნიერო ჟურნალი

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

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

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

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

წყარო: USACO, 2002/03, DEC, GREEN


ძროხებმა  სამეცნიერო  ჟურნალის  გამომცემლობა  გადაწყვიტეს.   ჟურნალი  შესდგება F (1 <= F <= 30) ნახაზისა და P (1 <= P <= 30) პარაგრაფისგან. მათგან თითოეული შეიცავს დასაბეჭდ  ზოლების გარკვეულ რაოდენობას  (1<= რაოდენობა<=100).  არცერთი  ნახაზი ან პარაგრაფი  არ შეიძლება  ისე  დიდი იყოს, რომ ცალკე აღებული  ერთ დასაბეჭდ გვერდზე ვერ მოთავსდეს. 

  საუკეთესო  ჟურნალებში  ნახაზების  ან პარაგრაფების  გვერდიდან  გვერდზე გადატანა დაუშვებლად  ითვლება.  ანუ  ისინი მთლიანად უნდა მოთავსდნენ გვერდზე, რომლის სიგრძე L  (1 <= L <= 100) საბეჭდი ზოლის ტოლია. პარაგრაფების და ნახაზების თანმიმდევრობა განსაზღვრულია მათი შემავალი მიმდევრობის შესაბამისად.  ყოველი ნახაზი  ბეჭდვისას  შესაძლებელია  დაშორებული  იქნას  შესაბამის პარაგრაფისაგან  არაუმეტეს  ერთი საბეჭდი  გვერდით (იბეჭდებიან წინა, იმავე ან მომდევნო გვერდზე). ნახაზის შესაბამისი ის პარაგრაფია, რომელიც მასზე მიუთითებს.

   მოძებნეთ ოპტიმალური განლაგება, რომელიც მინიმალურ საბეჭდ ზოლებსა და შესაბამისად ქაღალდს მოითხოვს.

შესატანი მონაცემები:

* სტრიქონი 1: შეიცავს სამ ჰარით დაშორებულ მთელს F, P და L.

* სტრიქონები  2..P+1: ყოველი სტრიქონი აღწერს პარაგრაფს: სტრიქონი 2 აღწერს 1 პარაგრაფს, სტრიქონი 3- მეორე პარაგრაფს და ა.შ. ყოველი სტრიქონი 

     შეიცავს ორ ჰარით გამოყოფილ მთელს: პარაგრაფის სიგრძეს საბეჭდ ზოლებში  და იმ ნახაზის ნომერს, რომელსაც ის მიმართავს. თუ პარაგრაფს ნახაზი არ

    შეესაბამისება, მასინ მითითებულია 0. ყოველ ნახაზი მხოლოდ ერთ პარაგრაფს  შეესაბამება. 

* სტრიქონები  P+2..P+F+1: ყოველი სტრიქონი აღწერს ერთ ნახაზს - მის სიგრძეს ერთი   მთელი რიცხვის სახით. სტრიქონი P+2 აღწერს ნახაზს 1,           სტრიქონი P+3 აღწერს ნახაზს 2 და ა.შ. 

გამომავალი ფაილის ფორმატი:  

ერთი სტრიქონი ჰარით გამოყოფილ ორი მთელი რიცხვით: ოპტიმალურ განლაგების მიხედვით დასაბეჭდი გვერდების და ბოლო გვერდზე საბეჭდი ზოლების რაოდენობებს. 




მაგალითები

შესატანი მონაცემები
2 4 20 10 1 7 0 9 2 3 0 12 11 დაკოპირება
გამოსატანი მონაცემები
4 3 დაკოპირება

შენიშვნა

ერთერთი ოპტიმალური განლაგება:

Page 1: Para 1, Para 2

Page 2: Fig 1

Page 3: Para 3, Fig 2

Page 4: Para 4