Wile E. Coyote is back. He is back in the business. The business of capturing the road runner. Being the most loyal customer to the Acme Corporation, they are hoping to do some great business with him. Although, Acme makes literally every kinds of devices, all of them has a similarity, that has been kept secret for ages. All of their products use a secret element “element X” (this is kept so secret that, only you and the Acme people know about this). The decision makers of the Acme Corp. has already estimated the maximum amount of element X that can be used into manufacture every month.

For month i, the per unit manufacturing cost of  “element X” is m_i, and at most n_i units can be produced. Moreover, the selling price for “element X” for that month is p_i. One more thing is that, element X older than E_i months can not be used. But good thing is that, they can store any amount of element X in their inventory (it's the Acme Corp, they can make anything :) ). Now, Acme Corporation wants to know how much element X should be produced and sold, to make the highest amount of profit.

Input

l        First line contains T, the number of test cases.

l        For each test case

u      First line contains two integers M and I, the number of months to consider and the cost of storing per unit of element X per month in the inventory.

u      Each of the next M lines describe the parameters for each month

·          The i^th line contains 5 integers, m_i, n_i, p_i, s_i, E_i, where m_i is the per unit manufacturing cost for monthi, n_i is the maximum amount that can be manufactured in this month, p_i is the selling price for that month(per unit), s_i is the maximum amount that can be sold that month, and E_i is the maximum time,element X manufactured on month i, can be stored in the inventory. For example, if for month 1, E₁ = 3, the elements produced in month 1 can be sold in months 1, 2, 3 and 4. But it can not be sold in month 5.

Output

For each test case, output the case number and the maximum amount of profit, Acme Corporation can make. Note that, you have to think of only M months. If any amount of element X is stored in the inventory after this period, are completely ignored. For formatting, see the sample input and output.

Constraints

l        

l        

l        

l        

Sample Input                                                                               Output for Sample Input

土匀匀的题解：

每个月拆点，从源点source到每个月x连一条流量为产量的边，然后每个月x'连一条到汇点sink连一条流量为销量的边，之后就是每个点x到x', (x+1)', (x+2)',(x+y)'连一条边，表示过0..y个月卖掉= =。

#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 2000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
#define Maxn 100010
typedef long long ll;

int T, M, I, m, n, p, s, E;
int From[Maxn], To[Maxn], Cost[Maxn], Flow[Maxn], Head[Maxn], Next[Maxn], Cnt;
int dis[Maxn], pre[Maxn], Queue[Maxn<<1], source, sink;
bool used[Maxn];

inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline int read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; }
//inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; }
inline void Insert(int u, int v, int w, int c)
{
	From[Cnt]=u; To[Cnt]=v; Flow[Cnt]=w; Cost[Cnt]=c; Next[Cnt]=Head[u]; Head[u]=Cnt++;
	From[Cnt]=v; To[Cnt]=u; Flow[Cnt]=0; Cost[Cnt]=-c; Next[Cnt]=Head[v]; Head[v]=Cnt++;
}

inline bool spfa()
{
	for (int i=source; i<=sink; i++) dis[i]=INF, used[i]=0; dis[source]=0; used[source]=1;
	Clear(pre, -1);
	int top=0, bot=1; Queue[bot]=source;
	while (top<=bot)
	{
		int u=Queue[++top]; used[u]=false;
		for (int p=Head[u]; p!=-1; p=Next[p])
		{
			int v=To[p];
			if ((Flow[p]>0) && (dis[v]>dis[u]+Cost[p]))
			{
				dis[v]=dis[u]+Cost[p];
				pre[v]=p;
				if (!used[v]) used[v]=1, Queue[++bot]=v;
			}
		}
	}
	return dis[sink]<0;
}

inline ll Mcmf()
{
	ll flow=0;
	while (spfa())
	{
		int aug=INF, u=sink;
		while (u!=source)
		{
			if (aug>Flow[pre[u]]) aug=Flow[pre[u]];
			u=From[pre[u]];
		}
		flow+=(ll)aug*dis[sink];
		u=sink;
		while (u!=source)
		{
			Flow[pre[u]]-=aug;
			Flow[pre[u]^1]+=aug;
			u=From[pre[u]];
		}
	}
	return flow;
}

int main()
{
	read(T);
	for (int _=1; _<=T; _++)
	{
		Clear(Head, -1); Cnt=0;
		read(M); read(I); source=0; sink=(M<<1)+1;
		for (int i=1; i<=M; i++)
		{
			read(m); read(n); read(p); read(s); read(E);
			Insert(source, i, n, m); Insert(i+M, sink, s, -p);
			for (int j=0; j<=E; j++) if (i+j<=M) Insert(i, M+i+j, INF, I*j);
		}
		printf("Case %d: %lld\n", _, -Mcmf());
	}