წონები

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

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

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

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

წყარო: პოლონეთი, ოლიმპიადა 14, ეტაპი 3


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

დაწერეთ პროგრამა რომელიც:

1. წაიკითხავს კონტეინერის გამძლეობებს და ხელსაწყოების წონებს რაც შემოგვდის.

2. გამოთვლის მაქსიმუმ რიცხვს იმისა თუ რამდენი ხელსაწყო შეიძლება გადავიტანოთ ამ კონტეინერების საშუალებით.

3. გამოიტანს პასუხს.

შესატანი მონაცემები:   პირველი ხაზი შეიცავს 2 რიცხვს n და m-ს(1<=n,m<=100,000), გამოტოვებული ერთი ადგილით. მიმდევრობით პირველი არის კონტეინერის, მეორე კი ხელსაწოების რაოდენობა. მეორე ხაზზე შემოგვდის n ცალი კონტეინერის გამძლეობა მილიგრამებში w (1<=w<=1,000,000,000). მესამე ხაზზე კი m ცალი ხელსაწყოს წონა j (1<=j<=1,000,000,000) ასევე მილიგრამებში.

გამოსატანი მონცემები: ერთი რიცხვი, რომელიც არის მაქსიმუმი რაოდენობა ხელსაწყოების, რომელთა გადატანაც შესაძლებელია მოცემული გამძლეობის მქონე კონტეინერებით.




მაგალითები

შესატანი მონაცემები
2 4 13 9 4 12 2 4 დაკოპირება
გამოსატანი მონაცემები
3 დაკოპირება