Berserker is a famous hero who has a lot of lives. In every life, he has some “blood points”. For example, he may have 100 blood points in his first life and 200 blood points in his second life. When Berserker loss all blood points in a life, he is killed. But he will become alive immediately with next life. When there is no next life left, Berserker is really dead and you win.
Saber can attack Berserker for N times. During each attack, Saber releases a fire bird to fight Berserker. Each fire bird has some “power points”.
A fire bird can make Berserker loss blood points. But if Berserker loss one blood point, the fire bird also will loss one power point. When the power points of a fire bird become zero, the fire bird dies.
A living fire bird may be in two statuses:“young”or “old”.
When a fire bird is just released, it is “young”. After it kills Berserker once or more, it becomes“old”.
Let’s suppose a fire bird with remaining n power points fighting Berserker with remaining m blood points in his current life:
If n> m: Berserker will be killed and becomes alive immediately with his next life(if he has), and then the fire bird will be“old”and fight Berserker again with remaining n-m power points.

If n = m: Berserker will be killed and becomes alive with his next life (if he has), and the fire bird dies.

If n < m: In this situation, if the fire bird is “young”, it will die after making Berserker loss n blood points. But if the fire bird is “old”, it just dies without doing any harm to Berserker.

As the “Master” of Saber, you can use “Command Mantra” M times. You can use “Command Mantra”to double a fire bird’s power points, but you can’t use “Command Mantra”more than once on a same fire bird. Now there is the question: How many times can you kill Berserker at most? 

The third line contains K integers, meaning the blood points of all Berserker’s lives. The first integer is for his first life, the second integer is for his second life, etc. 
Please note: 1<=N<=10000, 0<=M<=100, 0<=K<=100000. All power points and blood points are no more than 10000 and none negative. 

10 0 208 9 8 7 5 7 5 5 0 2 3 0 2 1 7 1 5 5 7 0 6 1 5 6 7 3 1 0 5 8 10 1 06 0 0 7 7 7 1 7 6 70 0 0

120大意为n个火球 和 k条命，每个火球可以攻击人1）如果火球血比人的大，那么火球杀死人，火球减去相应能量 2）入如果火球和人一样，那么人死掉，马上复活，球消失3）球血比较少，那么如果这个球第一次才出现，那么人减去相应生命，否则球立即消失4）有m次双倍杀伤，一个球只能一次双倍dp方程如下d[m][n] 表示m次双倍,n发火球杀死的最多人数，显然 d[m][n] = max(d[m][n-1]+w(n) , d[m-1][n-1]+w(2n) ), w(n)表示威力为n的火球接着上面状态能杀死的人数代码  1 /*    Fate Stay Night
  2     dp[m][n] = min( dp[m][n-1]+w(n) , dp[m-1][n-1]+w(2n) )
  3     m means double , n means fireball,
  4     and dp[m][n] has 2 values:number killed and remaining life
  5  */ 
  6 #include <cstdio>
  7 #include <cstring>
  8 #include <algorithm>
  9 #include <vector>
 10 
 11  using namespace std;
 12 
 13  #define maxn 100000
 14 typedef pair<int , int> PII;
 15 vector < int >  fire , life;
 16 PII dp[2][maxn+1];
 17 
 18 PII MAXP(PII a , PII b){
 19     if(a == b)return a;
 20     else if(a.first > b.first)return a;
 21     else if(b.first > a.first)return b;
 22     else if(a.second <= b.second)return a;
 23     return b;
 24 }
 25 
 26  /*now power can kill how many  and the rest life*/
 27 
 28 PII nextP(PII a, int power){
 29     int cnt=0 ,cur=a.first;
 30     PII t = a;
 31     int len = life.size();
 32     for(cur ; cur < len ; cur++)
 33     {
 34         /*power of fire > his life : kill him and restart(if he has life rest)*/
 35         if(power > t.second)
 36         {
 37             power -= t.second;
 38             t.first++;
 39             if(t.first < len)t.second  = life[ t.first ];
 40             cnt++;
 41             continue;
 42         }
 43         /*power of fire < his life: young time ?*/
 44         else if(power < t.second)
 45         {
 46             if(!cnt)t.second -= power;
 47         }
 48         /*= : kill him */
 49         else
 50         {
 51             t.first++;
 52             if(t.first < len)t.second = life[t.first ];
 53         }
 54         break;
 55     }
 56     if(cur == len)
 57     {
 58         t.first = len; t.second = 0;
 59     }
 60     return t;
 61 }
 62 
 63  int main(){
 64     int n , m , k , temp;
 65     while(1)
 66     {
 67         scanf("%d %d %d",&n,&m,&k);
 68         if(!n && !m && !k )break;
 69         life.clear();
 70         fire.clear();
 71         for(int i=0 ; i<n ; i++)
 72         {
 73             scanf("%d" , &temp);
 74             fire.push_back(temp);
 75         }
 76         for(int i=0 ; i<k ; i++)
 77         {
 78             scanf("%d" , &temp);
 79             life.push_back(temp);
 80         }
 81 
 82         if(k==0)
 83         {
 84             printf("0\n"); continue;
 85         }
 86         int ans = 0 ;
 87 
 88         dp[0][0]= make_pair(0,life[0]);
 89         dp[1][0] = dp[0][0];
 90         for(int i=1 ; i<=n ; i++)
 91         {
 92             dp[0][i] = nextP(dp[0][i-1] , fire[i-1]);
 93  //            printf("[%d %d]%d %d\n" , 0 , i , dp[0][i].first , dp[0][i].second);
 94         }
 95         for(int i=1 ; i<=m ; i++)
 96         {
 97             ans = 1-ans;
 98             for(int j=1 ; j<=n ; j++)
 99             {
100                 dp[ans][j] = MAXP( nextP( dp[1-ans][j-1] , 2*fire[j-1] ),  nextP( dp[ans][j-1] , fire[j-1] ) );
101             }
102         }
103         printf("%d\n" , dp[ans][n].first);
104 
105     }
106     return 0;
107 }