8

5 10
3 20
2 20
1 20
4 20
5 20

60

In the first sample, in order to obtain the optimal answer, you should act as follows.

• On the first day collect 3 fruits from the 1-st tree.
• On the second day collect 1 fruit from the 2-nd tree and 2 fruits from the 1-st tree.
• On the third day collect the remaining fruits from the 2-nd tree.

  In the second sample, you can only collect 60 fruits, the remaining fruit will simply wither.

  //31 ms	 0 KB
  #include
         
          
  #include
          
            using namespace std; struct node { int a,b; } s[3004]; bool cmp(node x,node y) { return x.a
           
            maxn) maxn=s[i].a; } sort(s,s+n,cmp); ans=0; for(i=1; i<=maxn+1; i++) { int r=v; for(int j=0;j
            
             =r) { s[j].b-=r; ans+=r; r=0; break; } else if(s[j].b) { r-=s[j].b; ans+=s[j].b; s[j].b=0; } if(!r)break; } } printf("%d\n",ans); } return 0; }
            
           
          
         

  
  C. Valera and Tubes time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

  Valera has got a rectangle table consisting of n rows and m columns. Valera numbered the table rows starting from one, from top to bottom and the columns ? starting from one, from left to right. We will represent cell that is on the intersection of row x and column y by a pair of integers (x,?y).

  Valera wants to place exactly k tubes on his rectangle table. A tube is such sequence of table cells (x1,?y1), (x2,?y2), ..., (xr,?yr), that:

  • r?≥?2;
  • for any integer i (1?≤?i?≤?r?-?1) the following equation |xi?-?xi?+?1|?+?|yi?-?yi?+?1|?=?1 holds;
  • each table cell, which belongs to the tube, must occur exactly once in the sequence.

    Valera thinks that the tubes are arranged in a fancy manner if the following conditions are fulfilled:

    • no pair of tubes has common cells;
    • each cell of the table belongs to some tube.

      Help Valera to arrange k tubes on his rectangle table in a fancy manner.

      Input

      The first line contains three space-separated integers n,?m,?k (2?≤?n,?m?≤?300; 2?≤?2k?≤?n?m) ― the number of rows, the number of columns and the number of tubes, correspondingly.

      Output

      Print k lines. In the i-th line print the description of the i-th tube: first print integer ri (the number of tube cells), then print 2ri integersxi1,?yi1,?xi2,?yi2,?...,?xiri,?yiri (the sequence of table cells).

      If there are multiple solutions, you can print any of them. It is guaranteed that at least one solution exists.

      Sample test(s) input

      3 3 3
      

      output

      3 1 1 1 2 1 3
      3 2 1 2 2 2 3
      3 3 1 3 2 3 3
      

      input

      2 3 1
      

      output

      6 1 1 1 2 1 3 2 3 2 2 2 1
      

      Note

      Picture for the first sample:

      

      Picture fZ??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vciB0aGUgc2Vjb25kIHNhbXBsZTo8L3A+CjxjZW50ZXI+PGltZyBjbGFzcz0="tex-graphics" src="http://www.cppentry.com/upload_files/article/49/1_8lg6b__.png" alt="\">
      

      模拟从第一个开始，蛇形输出，前k-1个输出两个格，最后一个将剩余的都输出。

      //46 ms	 0 KB
      #include
                 
                  
      int x[307],y[307];
      int main()
      {
          int n,m,k;
          while(scanf("%d%d%d",&n,&m,&k)!=EOF)
          {
              if(k>1)
              {
                  int count=0,x,y,flag=0;
                  for(int i=1; i<=n; i++)
                  {
                      for(int j=1; j<=m; j++)
                      {
                          if(count%2==0)printf("2");
                          count++;
                          if(i&1)printf(" %d %d",i,j);
                          else printf(" %d %d",i,m-j+1);
                          if(count%2==0)
                          {
                              printf("\n");
                          }
                          if(count==(k-1)*2)
                          {
                              x=i;
                              y=j;
                              flag=1;
                              break;
                          }
                      }
                      if(flag)break;
                  }
                  int a=m*n-count;
                  printf("%d",a);
                  for(int i=x; i<=n; i++)
                  {
                       for(int j=y+1; j<=m; j++)
                      {
                          if(i&1)printf(" %d %d",i,j);
                          else printf(" %d %d",i,m-j+1);
                          y=0;
                      }
                      y=0;
                  }
      
                  printf("\n");
              }
              else
              {
                  printf("%d",n*m);
                  for(int i=1;i<=n;i++)
                      for(int j=1;j<=m;j++)
                          if(i&1)printf(" %d %d",i,j);
                          else printf(" %d %d",i,m-j+1);
                  printf("\n");
              }
          }
          return 0;
      }