Algorithm

D. Cunning Gena
time limit per test
1 second
memory limit per test
256 megabytes
Problem link- https://codeforces.com/contest/417/problem/D
input
standard input
output
standard output

A boy named Gena really wants to get to the "Russian Code Cup" finals, or at least get a t-shirt. But the offered problems are too complex, so he made an arrangement with his n friends that they will solve the problems for him.

The participants are offered m problems on the contest. For each friend, Gena knows what problems he can solve. But Gena's friends won't agree to help Gena for nothing: the i-th friend asks Gena xi rubles for his help in solving all the problems he can. Also, the friend agreed to write a code for Gena only if Gena's computer is connected to at least ki monitors, each monitor costs b rubles.

Gena is careful with money, so he wants to spend as little money as possible to solve all the problems. Help Gena, tell him how to spend the smallest possible amount of money. Initially, there's no monitors connected to Gena's computer.

Input

The first line contains three integers n, m and b (1 ≤ n ≤ 100; 1 ≤ m ≤ 20; 1 ≤ b ≤ 109) — the number of Gena's friends, the number of problems and the cost of a single monitor.

The following 2n lines describe the friends. Lines number 2i and (2i + 1) contain the information about the i-th friend. The 2i-th line contains three integers xi, ki and mi (1 ≤ xi ≤ 109; 1 ≤ ki ≤ 109; 1 ≤ mi ≤ m) — the desired amount of money, monitors and the number of problems the friend can solve. The (2i + 1)-th line contains mi distinct positive integers — the numbers of problems that the i-th friend can solve. The problems are numbered from 1 to m.

Output

Print the minimum amount of money Gena needs to spend to solve all the problems. Or print -1, if this cannot be achieved.

Examples
input
Copy
2 2 1
100 1 1
2
100 2 1
1
output
Copy
202
input
Copy
3 2 5
100 1 1
1
100 1 1
2
200 1 2
1 2
output
Copy
205
input
Copy
1 2 1
1 1 1
1
output
Copy
-1



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

struct fri {
	int x, k, msk;

	bool operator<(fri f) {
		return k < f.k;
	}
};

int const N = 101;
int n, m, b, M, all;
long long dp[(1 << 20)];
fri fris[N];

int main() {
  scanf("%d %d %d", &n, &m, &b);
  M = (1 << m) - 1;
  for(int i = 0, m; i < n; ++i) {
  	scanf("%d %d %d", &fris[i].x, &fris[i].k, &m);
  	for(int j = 0, tmp; j < m; ++j) {
  		scanf("%d", &tmp);
  		--tmp;
  		fris[i].msk |= (1 << tmp);
  	}
  	all |= fris[i].msk;
  }

  if(__builtin_popcount(all) != m) {
  	puts("-1");
  	return 0;
  }

  sort(fris, fris + n);

  for(int i = 0; i < (1 << m); ++i)
  	dp[i] = 2e18;
  dp[0] = 0;

  long long res = 2e18;
  for(int i = 0; i < n; ++i) {
  	for(int j = 0; j < (1 << m); ++j)
  		if(dp[j] < 2e18)
  			dp[j | fris[i].msk] = min(dp[j | fris[i].msk], dp[j] + fris[i].x);

		if(dp[M] < 2e18)
			res = min(res, dp[M] + 1ll * b * fris[i].k);
  }

  if(res == 2e18)
  	puts("-1");
  else
  	printf("%lld\n", res);

  return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
2 2 1
100 1 1
2
100 2 1
1

Output

x
–
+
cmd
202
Advertisements

Demonstration

Codeforces Solution-Cunning Gena-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+