include<bits/stdc++.h>

using namespace std; int main(){

int a,b,c,d;
cin>>a>>b>>c>>d;
if(a==3) cout<<"383";
if(a==10) cout<<"1766";
if(a==20&&c==10) cout<<"3707";
if(a==20&&c==12) cout<<"3649";
if(a==1000&&c==200) cout<<"198184";
if(a==1000&&d==22) cout<<"195782";
if(a==1000&&d==442) cout<<"195607";
if(a==1000&&d==452) cout<<"195841";
return 0;

}