#include
#include
#include
#include
#include
using namespace std;
int main()
{
ifstream infile("heart.in");
ofstream outfile("heart.out");
while (true)
{
int numCities, minSoldiers;
infile >> numCities >> minSoldiers;
if (numCities == 0)
{
return 0;
}
//Adjacency list storing which cities are connected
vector > adjList(numCities);
//Has the city been removed from the graph?
vector removed(numCities);
//Number of soldiers stationed in the city
vector soldiers(numCities);
//Total number of soldiers defending the city
vector totalSoldiers(numCities);
for (int i = 0; i < numCities; i++)
{
int numNeighbors;
infile >> soldiers[i] >> numNeighbors;
for (int j = 0; j < numNeighbors; j++)
{
int neighbor;
infile >> neighbor;
adjList[i].push_back(neighbor);
}
}
//Calculate the total soldiers for each city
for (int i = 0; i < numCities; i++)
{
totalSoldiers[i] = soldiers[i];
for (int j = 0; j < adjList[i].size(); j++)
{
int neighbor = adjList[i][j];
totalSoldiers[i] += soldiers[neighbor];
}
}
//Queue containing cities that need to be removed from the heart
queue removeQ;
//Start with cities that already don't have enough soldiers
for (int i = 0; i < numCities; i++)
{
if (!removed[i] && totalSoldiers[i] < minSoldiers)
{
removeQ.push(i);
removed[i] = true;
}
}
//As we remove cities, see if their neighbors must now be removed
while (!removeQ.empty())
{
int badNode = removeQ.front();
removeQ.pop();
//Subtract the removed city's soldiers from its neighbors' defense
for (int i = 0; i < adjList[badNode].size(); i++)
{
int neighbor = adjList[badNode][i];
totalSoldiers[neighbor] -= soldiers[badNode];
//Does the neighbor now have too few soldiers?
if (!removed[neighbor] && totalSoldiers[neighbor] < minSoldiers)
{
removed[neighbor] = true;
removeQ.push(neighbor);
}
}
}
//number of cities in the heart
int numLeft = 0;
//number of soldiers in the heart
int numSoldiers = 0;
for (int i = 0; i < numCities; i++)
{
if (!removed[i])
{
numLeft++;
numSoldiers += soldiers[i];
}
}
outfile << numLeft << " " << numSoldiers << endl;
}
return 0;
}