消除连续1

import java.util.Scanner;
public class Main3 {
    public static int completeBag(Rule[] rules, int size) {
        int len = rules.length;
        int dp[][] = new int[len+1][size+1];
        // 遍历物品
        for (int i = 1; i <= rules.length; i++) {
            for (int j=0; j<=size; j++) {
                for (int k = 0; k*rules[i-1].count <= j; k++) {
                    // 放物品 0件-k件, 放或者不放
                    dp[i][j] = Math.max(dp[i][j],
                            dp[i-1][j-k*rules[i-1].count] + k*rules[i-1].score);
                }
            }
        }
        return dp[len][size];
    }
    public static int countMaxScore(Rule[] rules, String nums) {
        int count = 0;
        int ret = 0;
        for (int i = 0; i < nums.length(); i++) {
            if (nums.charAt(i)== '1') {
                count++;
            }else if (nums.charAt(i) == '0' && count > 0){
                // 可以选用多个规则
                ret += completeBag(rules, count);
                count = 0;
            }
        }
        return ret;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] arg = sc.nextLine().split(" ");
        int n = Integer.parseInt(arg[0]);
        int m = Integer.parseInt(arg[1]);
        String str = sc.nextLine();
        Rule[] rules = new Rule[m];
        for (int i = 0; i < m; i++) {
            int c = sc.nextInt();
            int s = sc.nextInt();
            rules[i] = new Rule(c, s);
        }
        str += "0";
        System.out.println(countMaxScore(rules, str));
    }
}
class Rule {
    public Rule(int count, int score) {
        this.count = count;
        this.score = score;
    }
    int count;
    int score;
}