---
# System prepended metadata

title: Backpack 4

---

# Backpack 4

Given $n$ gold bars, each bar has its own weight and cost. You have a backpack with a weight limit $S$. Calculate the maximum total cost of gold you can take at once, if it is **NOT allowed** to break the bars into parts. 

## Input format
The ﬁrst line of input contains two integers $S$ and $N$ ($1 \le S \le 10^4$; $1 \le N \le 300$). 
The second line contains $N$ integers — weights of the bars. Each bar has a non-negative weight not exceeding $10^5$.
The third line contains another $N$ integers — costs of the bars. Each bar has a non-negative cost not exceeding $10^5$.

## Output format
Print one integer — the maximum total cost of gold you can take at once.

## Sample

### Input
```
8 4
2 4 4 7
2 5 5 9
```

### Output
```
10
```

