მასივის დაყოფა

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

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

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

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


მოცემულია მთელი რიცხვებისაგან შედგენილი მასივი, რომელშიც ლუწი და კენტი რიცხვები თანაბრად არიან. თქვენ შეგიძლიათ ელემენტების გადანაცვლების გარეშე დაჰყოთ მასივი არაცარიელ ნაწილებად ისე, რომ თითოეულ ნაწილში ლუწი და კენტი რიცხვები ასევე თანაბრად გვხდებოდეს, თითოეული დაყოფის ღირებულება შეადგენს გაყოფის ადგილის მარჯვნივ და მარცხნივ მდებარე ელემენტების სხვაობათა მოდულს. დაყოფის შედეგად მივიღებთ უწყვეტი ინტერვალებისაგან შედგენილ მიმდევრობას. თქვენ გაქვთ გარკვეული თანხა და გამოთვალეთ რა მაქსიმალური რაოდენობის ნაწილად შეიძლება მასივის დაყოფა. მაგალითად, თუ გვაქვს მასივი 6 4 3 7 5 2 8 9 1 8, მისი გაყოფა შეიძლება დიეზით მითითებულ ადგილებში: 6 4 3 7 # 5 2 # 8 9 # 1 8. თუ არსებული თანხის რაოდენობაა 5, თქვენ შეძლებთ მასივის გაყოფას მხოლოდ პირველად მითითებული დიეზის ადგილას. სხვა ადგილას გაყოფისთვის თანხა არ გეყოფათ.

შესატანი მონაცემები: პირველ სტრიქონში ორი მთელი რიცხვი N (1<=N<=100) და K (1<=K<=1000). მომდევნო  სტრიქონში N მთელი რიცხვი. ამ რიცხვებიდან არცერთი არ აღემატება 100-ს.

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




მაგალითები

შესატანი მონაცემები
8 5 3 4 5 11 16 14 10 7 დაკოპირება
გამოსატანი მონაცემები
2 დაკოპირება
შესატანი მონაცემები
6 100 9 5 7 8 2 10 დაკოპირება
გამოსატანი მონაცემები
0 დაკოპირება