fork(1) download
  1.  
  2. import java.io.*;
  3. import java.util.*;
  4.  
  5. import static java.lang.Double.parseDouble;
  6. import static java.lang.Integer.parseInt;
  7. import static java.lang.Long.parseLong;
  8. import static java.lang.System.exit;
  9.  
  10.  
  11. public class Main {
  12.  
  13. static BufferedReader in;
  14. static PrintWriter out;
  15. static StringTokenizer tok;
  16. static boolean isLocal = false;
  17.  
  18.  
  19. class Item {
  20. String color;
  21. int cost;
  22. int value;
  23. int id;
  24.  
  25. public Item(String color, int cost, int value, int id) {
  26. this.color = color;
  27. this.cost = cost;
  28. this.value = value;
  29. this.id = id;
  30. }
  31. }
  32.  
  33. int n, dp_1 = -1000000;
  34. int budget;
  35. Item[] items;
  36.  
  37. boolean checkMax(int numW, int numBlue, int numR, int numBlack) {
  38. return numW <= 1 && numBlue <= 5 && numR <= 5 && numBlack <= 3;
  39. }
  40.  
  41. boolean checkMin(int numW, int numBlue, int numR, int numBlack) {
  42. return numW == 1 && numBlue >= 3 && numR >= 3 && numBlack >= 1;
  43. }
  44.  
  45. boolean canAddItem(Item item, int numW, int numBlue, int numR, int numBlack, int currSpent) {
  46. if (item.color.equals("W")) numW++;
  47. if (item.color.equals("Blue")) numBlue++;
  48. if (item.color.equals("R")) numR++;
  49. if (item.color.equals("Black")) numBlack++;
  50. currSpent += item.cost;
  51. return checkMax(numW, numBlue, numR, numBlack) && currSpent <= budget && numW + numBlue + numR + numBlack <= 12;
  52. }
  53.  
  54. int dp[][][][][][];
  55.  
  56. int go(int i, int numW, int numBlue, int numR, int numBlack, int currSpent) {
  57. if (n - i + numW + numBlue + numR + numBlack < 12) return -10000;
  58. if (i == n)
  59. return (checkMin(numW, numBlue, numR, numBlack) && numW + numBlue + numR + numBlack == 12) ? 0 : -10000;
  60. // if (dp[numW][numBlack][numR][numBlue][i][currSpent] != dp_1)
  61. // return dp[numW][numBlack][numR][numBlue][i][currSpent];
  62. int res = -10000;
  63. res = max(res, go((int) (i + 1), numW, numBlue, numR, numBlack, currSpent));
  64. if (canAddItem(items[i], numW, numBlue, numR, numBlack, currSpent)) {
  65. if (items[i].color.equals("W")) numW++;
  66. if (items[i].color.equals("Blue")) numBlue++;
  67. if (items[i].color.equals("R")) numR++;
  68. if (items[i].color.equals("Black")) numBlack++;
  69. res = max(res, items[i].value + go( i + 1, numW, numBlue, numR, numBlack, (items[i].cost + currSpent)));
  70. }
  71. return //dp[numW][numBlack][numR][numBlue][i][currSpent] =
  72. res;
  73. }
  74.  
  75. int ans;
  76.  
  77. void Case() throws IOException {
  78. n = nextInt();
  79. budget = nextInt();
  80. items = new Item[n];
  81. for (int i = 0; i < n; i++) items[i] = new Item(next(), nextInt(), nextInt(), nextInt());
  82. dp = new int[2][4][6][6][n][budget + 1];
  83. for (int a = 0; a <= 1; a++)
  84. for (int i = 0; i <= 3; i++)
  85. for (int j = 0; j <= 5; j++)
  86. for (int k = 0; k <= 5; k++)
  87. for (int l = 0; l < n; l++)
  88. for (int m = 0; m <= budget; m++)
  89. dp[a][i][j][k][l][m] = dp_1;
  90. ans = go( 0, 0, 0, 0, 0, 0);
  91. out.println(ans);
  92. out.flush();
  93. }
  94.  
  95.  
  96. void solve() throws Exception {
  97. int t = nextInt();
  98. while (t-- > 0) Case();
  99. }
  100.  
  101. private int gcd(int a, int b) {
  102. while (b > 0) {
  103. int temp = b;
  104. b = a % b;
  105. a = temp;
  106. }
  107. return a;
  108. }
  109.  
  110. int min(int x, int y) {
  111. return Integer.min(x, y);
  112. }
  113.  
  114. int max(int x, int y) {
  115. return Integer.max(x, y);
  116. }
  117.  
  118. long min(long x, long y) {
  119. return Long.min(x, y);
  120. }
  121.  
  122. long max(long x, long y) {
  123. return Long.max(x, y);
  124. }
  125.  
  126. int[] sort(int[] arr) {
  127. sort(arr, 0, arr.length - 1);
  128. return arr;
  129. }
  130.  
  131. void sort(int arr[], int l, int r) {
  132. if (l < r) {
  133. int m = (l + r) / 2;
  134. sort(arr, l, m);
  135. sort(arr, m + 1, r);
  136. merge(arr, l, m, r);
  137. }
  138. }
  139.  
  140. void merge(int arr[], int l, int m, int r) {
  141. int n1 = m - l + 1;
  142. int n2 = r - m;
  143. int L[] = new int[n1];
  144. int R[] = new int[n2];
  145. for (int i = 0; i < n1; ++i)
  146. L[i] = arr[l + i];
  147. for (int j = 0; j < n2; ++j)
  148. R[j] = arr[m + 1 + j];
  149. int i = 0, j = 0;
  150. int k = l;
  151. while (i < n1 && j < n2) {
  152. if (L[i] <= R[j]) {
  153. arr[k] = L[i];
  154. i++;
  155. } else {
  156. arr[k] = R[j];
  157. j++;
  158. }
  159. k++;
  160. }
  161. while (i < n1) {
  162. arr[k] = L[i];
  163. i++;
  164. k++;
  165. }
  166. while (j < n2) {
  167. arr[k] = R[j];
  168. j++;
  169. k++;
  170. }
  171. }
  172.  
  173. class Seg implements Comparable<Seg> {
  174. int st, end;
  175.  
  176. public Seg(int st, int end) {
  177. this.st = st;
  178. this.end = end;
  179. }
  180.  
  181. @Override
  182. public boolean equals(Object o) {
  183. if (this == o) return true;
  184. if (o == null || getClass() != o.getClass()) return false;
  185. Seg seg = (Seg) o;
  186. return st == seg.st &&
  187. end == seg.end;
  188. }
  189.  
  190. @Override
  191. public int hashCode() {
  192. return Objects.hash(st, end);
  193. }
  194.  
  195. @Override
  196. public int compareTo(Seg seg) {
  197. return st == seg.st ? Integer.compare(end, seg.end) : Integer.compare(st, seg.st);
  198. }
  199. }
  200.  
  201. private int[] na(int n) throws IOException {
  202. int[] a = new int[n];
  203. for (int i = 0; i < n; i++) a[i] = nextInt();
  204. return a;
  205. }
  206.  
  207. private long[] nal(int n) throws IOException {
  208. long[] a = new long[n];
  209. for (int i = 0; i < n; i++) a[i] = nextLong();
  210. return a;
  211. }
  212.  
  213. int nextInt() throws IOException {
  214. return parseInt(next());
  215. }
  216.  
  217. long nextLong() throws IOException {
  218. return parseLong(next());
  219. }
  220.  
  221. double nextDouble() throws IOException {
  222. return parseDouble(next());
  223. }
  224.  
  225. String next() throws IOException {
  226. while (tok == null || !tok.hasMoreTokens()) {
  227. tok = new StringTokenizer(in.readLine());
  228. }
  229. return tok.nextToken();
  230. }
  231.  
  232. public static void main(String[] args) throws Exception {
  233. try {
  234. if (isLocal) {
  235. in = new BufferedReader(new FileReader("src/tests/sol.in"));
  236. out = new PrintWriter(new BufferedWriter(new FileWriter("src/tests/sol.out")));
  237. } else {
  238. out = new PrintWriter(new OutputStreamWriter(System.out));
  239. }
  240. // long lStartTime = System.currentTimeMillis();
  241. new Main().solve();
  242. // long lEndTime = System.currentTimeMillis();
  243. // out.println("Elapsed time in seconds: " + (double) (lEndTime - lStartTime) / 1000.0);
  244. in.close();
  245. out.close();
  246. } catch (Throwable e) {
  247. e.printStackTrace();
  248. exit(1);
  249. }
  250. }
  251. }
  252.  
Success #stdin #stdout 0.32s 61468KB
stdin
1
20 1000
Black 52 11 1
Blue 43 8 2
Blue 72 0 3
Blue 97 0 4
W 72 14 5
R 94 10 6
R 75 15 7
Blue 110 17 8
Black 61 17 9
R 56 3 10
Black 120 2 11
R 108 15 12
R 116 13 13
R 70 3 14
Blue 118 10 15
R 97 2 16
R 40 17 17
W 76 11 18
Black 60 7 19
Blue 108 12 20
stdout
159