2112312312321321

import java.util.*; import java.util.stream.Collectors; // 大礼包 public class Problem23 { static List price = new ArrayList<>(); static List> specials = new ArrayList<>(); static int trackCost = 0; static int minCost = Integer.MAX_VALUE; public static void main(String[] args) { Scanner sc = new Scanner(System.in); List priceAndNum = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::valueOf).boxed().collect(Collectors.toList()); int num = 0; for (int i = 0; i < priceAndNum.size(); i++) { if (i == priceAndNum.size()-1) { num = priceAndNum.get(i); } else { price.add(priceAndNum.get(i)); } } for (int i=1; i<=num; i++) { specials.add(Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::valueOf).boxed().collect(Collectors.toList())); } List needs = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::valueOf).boxed().collect(Collectors.toList()); List> newSpecials = new ArrayList<>(); for (int i = 0; i < specials.size(); i++) { List special = specials.get(i); int cost = 0; for (int j = 0; j < special.size() - 1; j++) { cost += special.get(j) * price.get(j); } if (cost > special.get(special.size() - 1)) { newSpecials.add(special); } } backtrack(needs, 0); System.out.println(minCost); } static void backtrack(List needs, int start) { if (trackCost >= minCost) { return; } boolean haveUsedSpecial = false; for (int i = start; i < specials.size(); i++) { List targetSpecial = specials.get(i); if (!canUseSpecial(targetSpecial, needs)) { continue; } haveUsedSpecial = true; for (int j = 0; j < needs.size(); j++) { needs.set(j, needs.get(j) - targetSpecial.get(j)); } trackCost += targetSpecial.get(targetSpecial.size() - 1); backtrack(needs, i); for (int j = 0; j < needs.size(); j++) { needs.set(j, needs.get(j) + targetSpecial.get(j)); } trackCost -= targetSpecial.get(targetSpecial.size() - 1); } if (!haveUsedSpecial) { int sum = 0; for (int i = 0; i < needs.size(); i++) { sum += needs.get(i) * price.get(i); } minCost = Math.min(minCost, sum + trackCost); } } static boolean canUseSpecial(List special, List need) { for (int i = 0; i < need.size(); i++) { if (need.get(i) < special.get(i)) { return false; } } return true; } }