მხოლოდ ზურგჩანთა

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

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

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

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


დაწერეთ ზურგჩანთის დისკრეტული ალგორითმი.
 
შესატანი მონაცემები: პირველ სტრიქონში ორი მთელი რიცხვი 1 ≤ W ≤ 10000 და 1 ≤ n ≤ 300 — ზურგჩანთის ტევადობა და საგნების რაოდენობა. მეორე სტრიქონში n მთელი რიცხვი 0 ≤ w1,…,wn ≤ 100000, რომლებიც მიუთითებენ საგნების წონებს.

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

 

 




მაგალითები

შესატანი მონაცემები
10 3 1 4 8 დაკოპირება
გამოსატანი მონაცემები
9 დაკოპირება