Description

 

Input

Output

Sample Input

Sample Output

8

HINT

Source

唉这么蠢的Dp没一下子看出来，Dp真是太弱了啦。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 int f1[5050],eat[5050][5050],f2[5050]; 7 int n,h,d; 8 int read() 9 {10     int ans=0;char c;11     while ((c=getchar())==' ' || c=='\n' || c=='\r');12     ans=c-'0';13     while (isdigit(c=getchar()))    ans=ans*10+c-'0';14     return ans;15 }16 17 int main()18 {19     n=read();h=read();d=read();20     for (int i=1;i<=n;i++)21     {22         int x;23         x=read();24         for (int j=1;j<=x;j++)25         {26             int a;27             a=read();28             eat[i][a]++;29         }30     }31     for (int i=h;i>=1;i--)32     {33         int t=i+d<=h?f1[i+d]:0;34         for (int j=1;j<=n;j++)35         {36             f2[j]=max(f2[j],t)+eat[j][i];37             f1[i]=max(f1[i],f2[j]);38         }39     }40     printf("%d\n",f1[1]);41     return 0;42 }