package icm; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.AbstractMap; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Map; import java.util.Map.Entry; import java.util.stream.Collectors; public class Pickpockets { static int maxProfit = 0; public static void main(String args[]) { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] line1; String[] line2; List> teams = new ArrayList<>(); try { line1 = br.readLine().split(" "); line2 = br.readLine().split(" "); List days = Arrays.asList(line2).stream().map(Integer::parseInt).collect(Collectors.toList()); int H = Integer.parseInt(line1[0]); int T = Integer.parseInt(line1[1]); for (int i = 0; i < T; i++) { String[] lineX = br.readLine().split(" "); teams.add( new AbstractMap.SimpleImmutableEntry<>(Integer.parseInt(lineX[0]), Integer.parseInt(lineX[1]))); } maxPick(days, H, teams, 0); System.out.println(maxProfit); } catch (Exception e) { e.printStackTrace(); } } static void maxPick(List days, int H, List> teams, int profit) { if (days.stream().filter(d -> d > 0).findAny().isEmpty()) { maxProfit = max(maxProfit, profit); return; } for (Map.Entry team : teams) { for (int i = 0; i <= H - team.getKey(); i++) { boolean matchE = true; List newDays = new ArrayList<>(days); for (int j = 0; j < team.getKey(); j++) { if (newDays.get(j + i) > 0) { newDays.set(j + i, newDays.get(j + i) - 1); matchE = true; } else { matchE = false; break; } } if (matchE) { List> newTeams = new ArrayList<>(teams); newTeams.remove(team); maxPick(newDays, H, newTeams, profit + team.getValue()); } } } // maxProfit = max(maxProfit, profit); boolean same_nuly = true; for (int i=0; i < H; i++){ if (days.get(i) > 0) same_nuly = false; } if (same_nuly){ maxProfit = max(maxProfit, profit); } } static int max(int a, int b) { return (a > b) ? a : b; } }