ვაშლების დაჭერა

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

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

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

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

წყარო: USACO, 2004/05, NOV, QUAL


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

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

ვაშლები ცვივა (წუთში ერთი ცალი) T (1 <= T <= 1,000) წუთის განმავლობაში. ბესის შეუძლია ერთი ხიდან მეორემდე გადარბენა არაუმეტეს W-ჯერ (1 <= W <= 30). მოცემულია, თუ რომელ წუთს რომელი ხიდან ვარდება ვაშლი. განსაზღვრეთ ვაშლების მაქსიმალური რაოდენობა, რომლის შეჭმაც შეუძლია ბესის. 
ბესი დასაწყისში დგას 1-ლი ხის ქვეშ.

 შეტანის ფორმატი:

 * სტრიქონი 1:ჰარით გამოყოფილი ორი მთელი რიცხვი: T და W

 * სტრიქონები 2..T+1: 1 ან 2: the იმ ხის ნომერი, რომლიდანაც უნდა ჩამოვარდეს მორიგი ვაშლი.

  გამოტანის ფორმატი:

  * სტრიქონი 1: ბესის მიერ შეჭმული ვაშლების მაქსიმალური რაოდენობა მოცემულ პირობებში.

 




მაგალითები

შესატანი მონაცემები
7 2 2 1 1 2 2 1 1 დაკოპირება
გამოსატანი მონაცემები
6 დაკოპირება

შენიშვნა

სულ შვიდი ვაშლი ვარდება. პირველად მე-2 ხიდან, შემდეგ ორი ცალი ზედიზედ პირველი ხიდან, შემდეგ ორი ცალი ზედიზედ მე-2 ხიდან და ბოლოს ორი ცალი ზედიზედ პირველი ხიდან.

ბესი უნდა დაელოდოს, სანამ პირველი ხიდან ორი ცალი ვაშლი ჩამოვარდება, შემდეგ გადაირბინოს მეორე ხესთან  და ჩამოვარდნილი ორი ცალი ვაშლი გადასანსლოს, შემდეგ კი დაბრუნდეს და ისევ პირველი ხის ქვეშ შეჭამოს ბოლო ორი ცალი ვაშლი.