package question;

public class Question474 {
 public static void main(String[] args) {
 String[] strings = new String[]{"10", "0001", "111001", "1", "0"};
 System.out.println(new Question474().findMaxForm(strings, 5, 3));
 }

 public int findMaxForm(String[] strs, int m, int n) {
 Str[] strs1 = new Str[strs.length];
 for (int i = 0; i < strs.length; i++) {
 int a = 0, b = 0;
 for (int j = 0; j < strs[i].length(); j++) {
 if (strs[i].charAt(j) == '1') a++;
 else b++;
 }
 strs1[i] = new Str(a, b);
 }
 int[][] dp = new int[n + 1][m + 1];
 for (int i = 0; i < strs1.length; i++) {
 for (int j = n; j >= strs1[i].one; j--) {
 for (int k = m; k >= strs1[i].zero; k--) {
 dp[j][k] = Math.max(dp[j][k], dp[j - strs1[i].one][k - strs1[i].zero] + 1);
 }
 }
 }
 return dp[n][m];
 }
}

class Str {
 int one;
 int zero;

 public Str(int one, int zero) {
 this.one = one;
 this.zero = zero;
 }
}