#include <bits/stdc++.h>
using namespace std;
int main()
{
    char s[10];
    if(!cin.getline(s,10)){
        printf("0\n");
        return 0;
    }
    int l = strlen(s);
    if(l <= 0){
        printf("0\n");
        return 0;
    }
    sort(s, s+l);
    set<string> st;
    do{
        string t = "";
        for(int i = 0 ; i < l ; i++){
            t += s[i];
        }
        st.insert(t);
    }while(next_permutation(s, s+l));
    int ans = st.size();
    printf("%d\n",ans);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100500
struct node{
    char c;
    node *next;
    node(char cc):c(cc),next(NULL){}
};
char s[MAXN];
int n;
int main()
{
    scanf("%s", s);
    scanf("%d",&n);
    int l = strlen(s);
    node *head = new node(' ');
    node *p = head;
    for(int i = 0 ; i < l ; i++){
        node * q = new node(s[i]);
        p->next = q;
        p = p->next;
    }
    for(int k = 0 ; k < n ; k++){
        p = head;
        while(p->next && p->next->next && (p->next->c <= p->next->next->c)){
            p = p->next;
        }
        node *q = p->next->next;
        p->next = q;
    }
    p = head->next;
    while(p){
        printf("%c", p->c);
        p = p->next;
    }
    printf("\n");
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define MAXN 1005
struct node{
    int x,l,t;
    node(){}
    node(int xx,int ll,int tt):x(xx),l(ll),t(tt){}
    bool operator < (const node a) const{
        if(l == a.l) return t < a.t;
        return l > a.l;
    }
};
vector<node> a[MAXN];
int k,n,m;
int ans;

int main()
{
    int s,d,l,t;
    scanf("%d",&k);
    scanf("%d",&n);
    scanf("%d",&m);
    for(int i = 0 ; i < m ; i++){
        scanf("%d %d %d %d", &s, &d, &l, &t);
        s--;
        d--;
        a[s].push_back(node(d,l,t));
    }
    priority_queue<node> que;
    que.push(node(0,0,0));
    ans = -1;
    while(!que.empty()){
        node now = que.top();
        que.pop();
        if(now.x == n-1){
            ans = now.l;
            break;
        }
        for(int i = 0 ; i < a[now.x].size() ; i++){
            if(now.t + a[now.x][i].t > k)
                continue;
            que.push(node(a[now.x][i].x, now.l + a[now.x][i].l, now.t+a[now.x][i].t));
        }
    }
    printf("%d\n",ans);
    return 0;
}