Andy the Goat is at it again! He has found himself on a hazardous footpath containing several missing stones. More specifically, the footpath can be modeled as a binary string of length ~n~, where a 1 means there is a stone and a 0 means there is not a stone (in that location). Andy starts at the first location which will always be 1. Furthermore, Andy has ~m~ jumps that he can perform. Each jump is characterised by its length and energy cost.

Andy wants to make it to the final stone on the footpath (which will also always be 1). He wants to do this using the least amount of energy - that is, with a set of jumps with the smallest possible sum of energy costs. What is the minimum energy with which Andy can reach the end? If it is not possible for him to reach the end, output -1.

Input Format

The first line of input will consist of two integers, ~n~ and ~m~. The next line will consist of ~n~ digits, each of which is either 0 or 1. The first and last of these will always be 1. The next ~m~ lines will consist of two integers each ~a~ and ~b~, representing the length and energy cost of each jump.

Output Format

The output should consist of a single integer, the minimum energy used to reach the end (or -1 if this is impossible).

Sample Input

9 2
100101001
5 2
2 3

Sample Output

7

Sample Explanation

Andy jumps from the first stone to the sixth (length 5), with cost 2. Then, Andy jumps from the sixth to the fourth (length 2), with cost 3. Finally, he jumps to the final stone (length 5) with cost 2. Together, this sums to a total cost of 7. This is the minimal energy cost with which he can reach the end.

Constraints

$$\displaystyle 2 \le n \le 10^5 $$

$$\displaystyle 1 \le m \le 50 $$

$$\displaystyle 1 \le a \le n$$

$$\displaystyle 1 \le b \le 100$$