#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int N, M, K;
    cin >> N >> M >> K;
    vector<int> T(N);
    for(int i=0;i<N;i++) cin >> T[i];
    vector<int> D(K);
    for(int i=0;i<K;i++) cin >> D[i];
 
    const int MAXSUM = 1000*1000 + 10;
    bitset<MAXSUM> possible;
    possible[0] = 1;
 
    for(int t : T) {
        bitset<MAXSUM> shifted = possible;
        for(int k=1;k<=M;k++) {
            shifted <<= t;
            possible |= shifted;
        }
    }
 
    int ans = 0;
    int minD = D[0], maxD = D[K-1];
 
    for(int F1 = 0; F1 + maxD < MAXSUM; F1++) {
        bool ok = true;
        // F1 + D[i] 모두 만들 수 있어야 함
        for(int i=0;i<K;i++){
            if(!possible[F1 + D[i]]) { ok = false; break; }
        }
        if(!ok) continue;
 
        // 범위 내에서 D에 없는 값이 만들어지면 안됨
        for(int diff = minD; diff <= maxD; diff++){
            if(!binary_search(D.begin(), D.end(), diff)){
                if(possible[F1 + diff]) { ok = false; break; }
            }
        }
        if(ok) ans++;
    }
    cout << ans << "\n";
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpIHsKICAgIGlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUoMCk7CgogICAgaW50IE4sIE0sIEs7CiAgICBjaW4gPj4gTiA+PiBNID4+IEs7CiAgICB2ZWN0b3I8aW50PiBUKE4pOwogICAgZm9yKGludCBpPTA7aTxOO2krKykgY2luID4+IFRbaV07CiAgICB2ZWN0b3I8aW50PiBEKEspOwogICAgZm9yKGludCBpPTA7aTxLO2krKykgY2luID4+IERbaV07CgogICAgY29uc3QgaW50IE1BWFNVTSA9IDEwMDAqMTAwMCArIDEwOwogICAgYml0c2V0PE1BWFNVTT4gcG9zc2libGU7CiAgICBwb3NzaWJsZVswXSA9IDE7CgogICAgZm9yKGludCB0IDogVCkgewogICAgICAgIGJpdHNldDxNQVhTVU0+IHNoaWZ0ZWQgPSBwb3NzaWJsZTsKICAgICAgICBmb3IoaW50IGs9MTtrPD1NO2srKykgewogICAgICAgICAgICBzaGlmdGVkIDw8PSB0OwogICAgICAgICAgICBwb3NzaWJsZSB8PSBzaGlmdGVkOwogICAgICAgIH0KICAgIH0KCiAgICBpbnQgYW5zID0gMDsKICAgIGludCBtaW5EID0gRFswXSwgbWF4RCA9IERbSy0xXTsKCiAgICBmb3IoaW50IEYxID0gMDsgRjEgKyBtYXhEIDwgTUFYU1VNOyBGMSsrKSB7CiAgICAgICAgYm9vbCBvayA9IHRydWU7CiAgICAgICAgLy8gRjEgKyBEW2ldIOuqqOuRkCDrp4zrk6Qg7IiYIOyeiOyWtOyVvCDtlagKICAgICAgICBmb3IoaW50IGk9MDtpPEs7aSsrKXsKICAgICAgICAgICAgaWYoIXBvc3NpYmxlW0YxICsgRFtpXV0pIHsgb2sgPSBmYWxzZTsgYnJlYWs7IH0KICAgICAgICB9CiAgICAgICAgaWYoIW9rKSBjb250aW51ZTsKCiAgICAgICAgLy8g67KU7JyEIOuCtOyXkOyEnCBE7JeQIOyXhuuKlCDqsJLsnbQg66eM65Ok7Ja07KeA66m0IOyViOuQqAogICAgICAgIGZvcihpbnQgZGlmZiA9IG1pbkQ7IGRpZmYgPD0gbWF4RDsgZGlmZisrKXsKICAgICAgICAgICAgaWYoIWJpbmFyeV9zZWFyY2goRC5iZWdpbigpLCBELmVuZCgpLCBkaWZmKSl7CiAgICAgICAgICAgICAgICBpZihwb3NzaWJsZVtGMSArIGRpZmZdKSB7IG9rID0gZmFsc2U7IGJyZWFrOyB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgaWYob2spIGFucysrOwogICAgfQogICAgY291dCA8PCBhbnMgPDwgIlxuIjsKfQ==

MiAzIDIKMSAzCjAgMg==

2 3 2
1 3
0 2