Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Budget Travel

By RasheedAbid · Limits 5s, 512 MB

You and your friends are always excited about travelling new destinations, specially if they are cheap.
You have shortlisted D destinations to travel and total possible expenses for everyone in each destination Di (1 <= i <= D). You have decided among yourselves that each person will bear the total expense of the group in a destination. Which means if you have N person in your group you will potentially choose N destinations and decide who will be responsible to bear the expenses for which destination.

While coming to a consensus, you realized that everyone has their own list of preferences which cities they are interested to bear the cost for.

In this problem you have to choose N destinations out of D destinations such that each person can bear the expense of exactly one destination which exists in the preferral destination of that person. Of course, the total sum of the expenses of all destinations must be minimal.


The first line of the input will be two positive integers D and N. The next line will have D number of integers. Each number Di denotes the total expenses for the group in i’th destination. For simplicity you can assume these are ids of destinations.
The next N lines will have information of the preferences of everyone in your group. Each line will start with Pi denoting the number of destinations i’th person prefers, followed by i number of integers ( 1 <= i’th integer <= D) denoting a destination id.

  • 1 <= D <= 1000
  • 1 <= N <= D
  • 1 <= Expense of a single destination <= 10000

The input will be such that there is always one possible way to reach a particular total sum. More formally it’s not possible to have total sum S by two possible sets of destinations s1 and s2.


Output should have one integer denoting the minimum total expenses of selected N destinations.
If it’s not possible to choose N destinations fulfilling the criteria print -1.


3 2
1 5 10
2 1 3
1 1



60% Solution Ratio

oneonetwotwoEarliest, Oct '17

dip_BRURFastest, 4.3s

mahbubcsejuLightest, 13 MB

dip_BRURShortest, 3572B


Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.