Je hebt een rugzak dat een maximum gewicht kan dragen. Er zijn items die je in je rugzak kan stoppen. Elk item heeft een waarde en gewicht. Bereken de maximale waarde die je in je rugzak kan stoppen zonder dat deze te zwaar wordt.
Elk item kan je of volledig in je rugzak stoppen of niet in je rugzak stoppen. Het is niet mogelijk een gedeelte van het item te gebruiken en je mag een item niet meerdere keren in je rugzak stoppen.
Elk item kan je of volledig in je rugzak stoppen of niet in je rugzak stoppen. Het is niet mogelijk een gedeelte van het item te gebruiken en je mag een item niet meerdere keren in je rugzak stoppen.
Invoer
- Eerste regel is het gewicht van de rugzak, dit is altijd een geheel getal
- Tweede regel is het aantal items n (0 < n <= 25).
- Op de derde regel staan n gehele getallen gescheiden met een spatie: dit zijn waardes van de items
- Op de vierde regel staan n gehele getallen gescheiden met een spatie: dit zijn de gewichten van de items
Uitvoer:
- De uitvoer is een geheel getal met de maximale waarde die je in je rugzak kan stoppen
Voorbeeld invoer:
10
4
10 40 30 50
5 4 6 3
Voorbeeld uitvoer:
90