#include<bits/stdc++.h>
using namespace std;
int n;
int dp[1001][100001];
vector<int>prices,pages;
int dfs(int i,int x){
    if(x==0||i>=prices.size())return 0;
    if(dp[i][x]!=-1)return dp[i][x];
    int ans=dfs(i+1,x);
    if(x-prices[i]>=0)
     ans=max(ans,dfs(i+1,x-prices[i])+pages[i]);
    /*for(int k=i+1;k<prices.size();k++){
        if(x-prices[k]>=0)
        ans=max(ans,dfs(k,x-prices[k])+pages[k]);
    }*/
    return dp[i][x]=ans;
}
int main(){
  int n,x;
  memset(dp,-1,sizeof(dp));
  scanf("%d%d",&n,&x);
  prices.push_back(0);
  pages.push_back(0);
  for(int i=0;i<n;i++){
      int a;
      scanf("%d",&a);
      prices.push_back(a);
  }
  for(int i=0;i<n;i++){
      int a;
      scanf("%d",&a),
      pages.push_back(a);
  }
  cout<<dfs(0,x);
}

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IG47CmludCBkcFsxMDAxXVsxMDAwMDFdOwp2ZWN0b3I8aW50PnByaWNlcyxwYWdlczsKaW50IGRmcyhpbnQgaSxpbnQgeCl7CiAgICBpZih4PT0wfHxpPj1wcmljZXMuc2l6ZSgpKXJldHVybiAwOwogICAgaWYoZHBbaV1beF0hPS0xKXJldHVybiBkcFtpXVt4XTsKICAgIGludCBhbnM9ZGZzKGkrMSx4KTsKICAgIGlmKHgtcHJpY2VzW2ldPj0wKQogICAgIGFucz1tYXgoYW5zLGRmcyhpKzEseC1wcmljZXNbaV0pK3BhZ2VzW2ldKTsKICAgIC8qZm9yKGludCBrPWkrMTtrPHByaWNlcy5zaXplKCk7aysrKXsKICAgICAgICBpZih4LXByaWNlc1trXT49MCkKICAgICAgICBhbnM9bWF4KGFucyxkZnMoayx4LXByaWNlc1trXSkrcGFnZXNba10pOwogICAgfSovCiAgICByZXR1cm4gZHBbaV1beF09YW5zOwp9CmludCBtYWluKCl7CiAgaW50IG4seDsKICBtZW1zZXQoZHAsLTEsc2l6ZW9mKGRwKSk7CiAgc2NhbmYoIiVkJWQiLCZuLCZ4KTsKICBwcmljZXMucHVzaF9iYWNrKDApOwogIHBhZ2VzLnB1c2hfYmFjaygwKTsKICBmb3IoaW50IGk9MDtpPG47aSsrKXsKICAgICAgaW50IGE7CiAgICAgIHNjYW5mKCIlZCIsJmEpOwogICAgICBwcmljZXMucHVzaF9iYWNrKGEpOwogIH0KICBmb3IoaW50IGk9MDtpPG47aSsrKXsKICAgICAgaW50IGE7CiAgICAgIHNjYW5mKCIlZCIsJmEpLAogICAgICBwYWdlcy5wdXNoX2JhY2soYSk7CiAgfQogIGNvdXQ8PGRmcygwLHgpOwp9

MTAwMCAxMDAwMDAKMzMgNzA5IDg1MCA3MjQgMzI2IDMxMiAyMDAgNTM4IDY3MCAxNzYgMTQyIDk2MSA0NCAyNjYgMjk1IDYwNSA1IDgyNyAxMTAgNzA3IDU2NSAyMzkgOTk3IDkxNyAyODMgMTY1IDU3NCA4MyAyNjYgNTE2IDkzNiA1MDMgMzczIDE1NyA4MjQgNDM0IDU5NyA4ODcgNDM1IDIxMiA3ODcgOTg0IDgyMSAyMSA1MTYgNjg5IDIxNiA5MDYgODk2IDY1MiAzODkgNzE1IDQwMSA1NjUgMzMwIDEyIDQ2OCA4NjEgMTg4IDMwNyAxOTMgNTg5IDk4MiAzNCA2MjMgMzg0IDEyNiA2MzMgNjY1IDc2MiA0NjMgOTk4IDEzNCA0NDUgODIwIDM3MSA3NjQgMjk5IDM2NSA5NSA2MDMgOTgwIDIzNiA5NTEgMjkzIDgxMyA0NjUgMzUgMTAxIDkxNiAyNDUgNTM0IDk1NiAyODAgMTM0IDk5NyA2NTcgNTMwIDM1NiA0MDMgODM0IDM5MCA5NjkgMzk2IDkxNSA2ODkgNjM2IDIzNiA3NDMgODMxIDgwNiAxIDU2NyA4MTggNzA4IDExNSA0NTUgNjE3IDQ0NSAyNDIgOTYwIDM1MCA5MTggNDA1IDQwNyA4NTMgODI0IDg5NyA0NjYgODg2IDQxNCA4MDEgMzg3IDM5NSA5NjQgOTUzIDUzMiAzMjAgNTQ4IDM5OSAzMzQgMzk0IDIwMiAyOSAxMzkgODEyIDM2NSAxOSA2NTYgNTcyIDM0NiAzNTAgMjM5IDg1MyAxMDkgNDY3IDg1MSA0OSA2MjQgMzUyIDg1OCA2NzYgODU0IDg0MSAxOSAxNiA0ODYgMTM5IDE0NSA3NjkgMzc5IDg0MCAyOTUgNjEzIDkzOCA0MSAyMDIgNTk2IDE1NiAxNzkgNjIxIDU1NSAxMTUgODE0IDY0OCA2NDggNDYwIDY0OSA1OTMgODEyIDkyNiA4MDMgNzggMzU2IDg4NSA4NzcgOTc2IDI4MCAxNDEgNjcyIDM5MSAzMTMgODQ2IDQzNCAyMjUgNjczIDY3NCAyOTggMzkwIDg4MCAzNiA4MTQgNiAxODYgNTQ1IDMzOCA1MDMgNTczIDE3MyA2ODggNDU3IDM2NyA5MjYgNTMwIDM2MCAxNSA1NDUgNDcwIDYxIDcxOCA2NjUgODc3IDM5OSA3MjEgNDkgMjggMjIzIDg0NiA2MDkgNjU3IDQ4OCA3MjggNjUxIDk0MSA0MCAxNjAgNjczIDkzIDM1MSAxMDkgMjI0IDI2MyAzNyA4MzkgNzExIDQzOSAyMzIgMzgwIDQ2NiA5NjEgNzE4IDIzOSAzMjcgNTI5IDc4MiA0ODcgNjgwIDc0NCA3NTYgMjc1IDcwMSA1MzAgODE0IDU3OSA3MjEgMzAgMzgxIDg3NiAyNjMgNjI4IDkgMTUwIDY4IDkwMiA4OCAxNDggMjY4IDQ0OCAzNDYgMzYzIDQ3MyAzODkgOTgzIDE5NSA0MzcgNTU0IDM0NSAyODMgNzM3IDc0NyA3NDUgNDMgMTYzIDQ1NiA1ODkgNTQ2IDQ3NyA3MzIgODI4IDM0IDI3MCA2NjkgMTQ4IDIzMyA2NTMgMjkyIDMwNiAzMTUgMjggNzA5IDg1OSAzOSAzNDkgMjkwIDUwMSA1MjEgNjg4IDc2NyA3MiA4NTUgNzc3IDQyMiAzOTIgOTQxIDcxMyA5MzUgOTU0IDI0MyAzMDIgODkgOTE0IDkxOCA1MjggODUzIDE0MSA4MjYgODA5IDY5NSA0NTUgODMyIDMxMyAzODcgODM5IDExIDczMSAzODMgODM0IDc3MyA3OTcgNjcxIDY2IDExOSAzOCA0MDYgODQzIDM2MSAyMSA5OCA1NDAgMjEgNzAwIDgyMCA0NTEgMzE2IDQ0NCAxMTUgOTA2IDcxNSAyNCAxMjEgOTQ4IDQ3NyA2NzYgNjMzIDY3MiA4OTcgNjUzIDUzNSA1IDQyNyAyNDggMzMxIDY1OCAzIDMyNiA3MDUgNTUgMzM5IDk2MCA0NjUgNDI4IDI5IDQzMiAzMjggNDU1IDk0IDYxMyA0MzUgNTczIDMzMSA1NjAgOTAyIDQ5NSA5MzYgMjU3IDc1NyA5MjggMTcgNTUgOTY3IDYyNiA1ODMgMjUzIDY1NyA5MjEgNDEwIDc4NiA5MzIgNzI3IDQ5NCA2MTUgMTc0IDcxOSAxOTMgNTUzIDU4OCAzMjUgNTQ0IDQyMiAxMDMgOTgyIDM5OSA4NzYgNDQ1IDQwNyAxNDYgMTUyIDEgOTI2IDkzMiA3MDcgMzU3IDcxNyA1NDAgOTE4IDc0MCA0MDYgOTExIDE2OCA4NCAzMDggODY1IDUyMyAzMTkgMTY4IDQwMyA1NzMgODQzIDM5NSAyMjIgNDIwIDkzNCAyOCA0NTEgMzY0IDg4IDM1NiA1NzggNzk0IDQ0IDgzNyA0MTkgOTQzIDg4NyA3NjUgNDU5IDE5IDg5IDU5NCA3NjMgMjYzIDM3NyA1NTkgNTg5IDM5NSAxOTEgNTUzIDI1MyA2MDUgMjMgODE1IDc5OCAzMTkgODU5IDE1NiA1NzQgMzQgNzAgODYwIDQzMyA2MDMgNjAwIDg4IDQyMyA0MTkgNDMxIDg1NiA5MTUgNTQ5IDUxOSA1MCA0NDYgNTY0IDM3NiAyMTUgODUyIDMgMzgzIDYxMyA0MzggNzM0IDQ1OCAxNTYgNjg5IDEwNSA3MjQgODQyIDUwOCA4MyAzODIgNzE1IDI1NSA4MTMgOTk4IDU5OSA4MTIgNDkyIDY1MyAzOTggMzUxIDUzNiA4MzIgMzM0IDc1MyA0MzggNzg4IDM2MCA4MSA4NDAgNDM0IDUyMyA0NCA2NzcgNzM4IDExMSA4NjYgMTQyIDMwIDIzOCAzMjEgOTQ2IDg1MSA2NDkgNzg5IDg3NyA2MDIgMzgxIDYzMCA2MDEgMTkzIDI3MiA0ODkgNzEgOTY2IDIzNiA5OTUgODAxIDM2NiA3NzYgOTYxIDg0NiA3OSA2NjggNDIzIDU2OSAxMjggMjUyIDcyNCA4MzAgMzEwIDQ4NCAzMjcgODMxIDkzMiA3MTEgNjYwIDU2MSA1OTkgNzg2IDY5IDE5OCA5MzEgODYwIDg5MiA5MzQgNzkgNzc0IDI3OSAyNzEgODk0IDg5NCAxODcgMjUwIDI2NiAzOTAgMjk2IDYzNyA4NDggMjA0IDg0MiA2OTYgNjI2IDEwMyA4ODcgMTQ4IDczOSA0MSA1NjAgOTQyIDk1NSAyIDc3NyA3MjEgMTIxIDI3MCAzMzggNDkyIDY2NiA0NjQgMTYwIDE4IDEyOCAyNyAzNjggODE4IDM3MCA0MzEgMjAgNjIxIDkyNiA0NTQgODY3IDExIDgxOSA4MjcgNjY0IDk2NiAxNSA2MjUgNTggODcwIDc0OSA0MTQgNjAgNTU4IDk2NiA1OTIgMjYxIDgyIDE2OSA1NCA2MzYgNTAwIDc1MCA3NDYgMjY4IDMwIDYxOSAzMjYgNzggODkxIDQ5OSA2NTUgNTcxIDY0NSA5MzUgOTY1IDQ5NCA5NjggNzc3IDk0NiA4MCA0MzkgNjExIDYyOCAxMjcgNDI4IDQ3MCAxMDUgODMzIDk5MSA1ODcgNDI5IDI5MSA0NyA4OTAgMzczIDcyIDU0MyA1MTMgNzc0IDg0NSA3MDAgMjU2IDY4MSA0MDAgNDE4IDE2IDE3MSAyMzAgODYzIDYwMiAzNjYgNDA1IDcxMCA4MjkgOTU0IDU5MSAyNjMgNzc2IDYyNiAxOTIgMTM5IDI2MSA1NDAgMTQ3IDk1NyA2ODQgMzcwIDk3NSA0NTUgMjYyIDc1NyAyMzYgMzY5IDEwMSA0NCA2MDQgMzI4IDcyNyAyMTQgMjE2IDkwNCAxMTAgODk5IDk2NyA5MzcgNjEgODE2IDc5NSAyMTEgNTM0IDM0IDk1OSA5NDEgMjg4IDQ5MCA1MDkgMTY0IDg3MCA2NjggNzQ1IDU1MiAyNTUgNDQ2IDE0MSA2OTQgNTcwIDUwOCAxNjIgMjY0IDIyOCA1NzEgNDg0IDEwIDY5OCA1NzAgOTM3IDUzOSA5NDIgMzUyIDIwMyA5ODkgNTc1IDY0OCAxNTIgNTQgOTk2IDg3MyA3ODMgNTQ3IDIxMyAyMzMgMjYzIDc5NyAyOTYgMzkxIDMwNyAxNzcgOTQwIDcyOSAxOCA3OTMgNzU5IDM1MiA2MTcgNDQ2IDg3MSA2MjEgNjYxIDE1NyA3NjkgODY3IDI4MSA1MTggNDY4IDMzMCAzNyA0MzUgNzc4IDM0NSA1NTAgNDkzIDc3IDYxNiA5MzQgNjMzIDQ0OSAxMDQgMjAwIDI0MCA3MzIgNjk5IDc0MyAyOTMgMzYzIDM4NSA5OTAgODkyIDUwMyA1MzggMiA1NTcgMzI3IDMyOSAzMTkgNTA0IDUwNyA0ODkgNDM1IDUxOCAyOTAgNDUxIDQ0MyA3NDUgNzIxIDgwIDY3MCA1MTcgODI0IDM0MiA4NjEgMjgxIDg5NyAxNTUgODQwIDk5IDU1OSAyMjIgNDAgOTMwIDcwNiA1MTAgOTg3IDMwIDQ0OCAzMzAgOTE1IDUyMyA3NTMgNjEwIDEgMjkwIDY4IDgzMiAxNzMgOTc4IDIyMCA2NjcgOTk3IDkyNCA2OCA2OTIgMzQ0IDM3NCA2NTYgNzIwIDEyNyAyNDAgNDU4IDY3OSA2MzIgNzExIDkwMSA2NTAgMjgwIDQ2MCAzODAgMTI4IDEwNiA2NjQgNzUxIDg2OSAyOTggMjM4IDg3MSA4NDMgOTc0IDQwNiA3NzEgNjQ4IDQyNyA5MTMgNTAzIDY4MiAxMzQgMTIyIDk5MiA1MDQgMzU4IDc4NyAzNDIgMjQwIDUzNiAyMjYgODEzIDQ2IDM4NSA5ODEgNDI2IDIzMCA5MzIgMzM0IDYxOCAxMSA2OTggMTk4IDQ4MCA3MzAgNzUwIDQ3NyAzOTUgODE0IDIwNCAxOTMgOTM0IDkxMyAzOTUgNDU0IDkyOCA0MzEgMjU1IDk2NCA0MiA0MiA3NzMgNDk4IDg1MyA2MDcgNTQwIDczNiA0NjAgODcwIDM1MSA2MTEgNTMwIDQ3NCAyNjQgNzY4IDc3Nwo4MDUgMjMxIDk0NiA3NjUgMzQ5IDU3NiAyNjcgODU3IDc0NiAxNDcgMTM4IDYzNCAzODMgNjQzIDg5NSAzNTUgOTMyIDI3MyAyNDcgNTYzIDkwNSA5NzQgNTUwIDY2OSAzODkgMjEzIDg5NyA1ODEgOTAyIDM3MyAxOTYgNDY0IDEwOSA2NSAyMTYgNjAyIDU0MCA0NzkgNzkwIDg5MCA0NSAxNjkgNTgyIDc0NCA5ODQgNTQgNjExIDc1MiAyMiAyNTYgNzQgMzIyIDc0NiAxNTAgMTEyIDY5OCA1NiA0MTMgNTQ5IDMyOCA4MjIgMTU0IDU5MyA1NDQgNzMgNjc4IDMyMiA5OTAgOTQ4IDg2OCA5NTAgNDE1IDI4MCA1NjMgMzQ0IDc0MCA1NTYgNDM5IDE5OSAyODggOTkyIDE1NyA2NzUgNiAxNTEgNjE2IDQ2MSA4NjQgMTc3IDc2MiAyNDAgMzEzIDY0MCA4NTQgNjQxIDg5MSA4OTUgODggOTg0IDQ0NSA0NTQgNzU4IDI2MyAzMTQgOSA5OTUgMjcxIDE5MiAxNTkgODI1IDI5MyA0MyA2MDIgNDkyIDY3MiAzMjcgNjQwIDU5MyA4MjYgMzgyIDcgNzExIDI2NSA0MCA1MTYgODE3IDQ5IDMxNiA2MDkgODQ5IDQyNCA1MjEgNDI0IDgyMyA1MjIgODY4IDEzMiA3MDAgMTYyIDE0NiA1MyA2MjYgODUxIDUyNSA0NzMgNTAwIDI1MCA0NDAgNDQ2IDYwMiA1NTAgMTc5IDg4MiA0OTAgOTE2IDUyNyAxMjAgNjY3IDE1MiA1ODIgNTMzIDI3MyA2MiA5NTUgOTgwIDY3MSA1MTIgMjggMTE0IDIyMSA1NTYgOTkwIDYxIDQ2MiA4MjIgNzI4IDYxNiA1MzcgNzUgMzIxIDc4MyAzNSA0NTcgNTQ4IDYwMSA0NTggMzQ4IDg1NiA0NzkgMTMgNjI0IDM0NCA4NjYgMjcxIDEzMyAxOTcgMzQ3IDY4IDY4NyA4MzMgMzgwIDU5MSA2NTIgMzMwIDY0NSA0NjggOTQ0IDY5MCA3ODEgMTAwIDI3OSAxMzcgMzkzIDk4OSAzMTAgMSA5NjcgMjM3IDk5MCA5OTcgMTc3IDIgOTQ4IDI5MyA0NzAgODQ0IDI2NCA5NDcgNDU3IDY2NiA4OTggNjM0IDQ5MCAzOTkgNjY1IDM5MyA4NTUgODQ5IDkxOCA1MDIgNTMxIDQxNCA0NTUgNTM0IDU3OCAxMzIgNDIwIDY5MiA5NTcgOTk0IDUyMSAxNTkgMTY2IDM2NCA3OTUgOTU0IDEzMyA1MTkgNzY3IDYxIDI4NyA3MzEgMzk0IDg0MCA0MTMgMjUwIDcxNyAzNDcgNjI5IDM0OCA0NzIgMzc5IDI2NCA4NTggNjYwIDUwNiA2MiA2NTMgOTY0IDQ5MSA0NjEgMTM5IDU5MyA4OTcgMjg4IDcyMSAxMDggNzczIDM5MyA3MjYgMTMyIDg3NyAyMTEgMjc0IDUxMCA0NTIgNTAwIDUxOCA1OTMgMzkxIDc0MCA0MDcgMTgyIDkyOCAzMiA0MDEgNjIgNzIwIDg1MiAzMjcgNTEyIDYyNiA0MjkgODQgNDg5IDgxMCAyOTAgNTUxIDE1NiAyNSA3MDEgMjQgODYwIDU5NiAyMTcgNTg5IDY4MiA3MiAyNDAgNjczIDE4MCA3OTYgODMyIDgyOCA4NTAgMTIyIDI2OSAzNzIgNTQ0IDQzIDk0MCAyNzYgNTQzIDI2MSA4MTMgMTggNTQgNzg4IDEzNSA2NSAxMTkgNzgxIDU2OCA0NzIgNzE3IDE3MSAzMzMgODg5IDQ4IDE1MCAyNTkgMzIyIDcyOSAyMyA5MTEgNzMgNjUyIDkyNCAxMDkgNTEwIDcwNiA1MDEgODkyIDM3OSAxMDAgNDU0IDM3OCA1NDUgMTA2IDcwNSA4NDcgMTcxIDc1NiA3NzYgODUxIDU3NSAyNjkgNDUxIDI2OSAzNzIgODg4IDg1NiA5NzIgODcgMTk1IDg1NiA1OTIgNTcxIDU3MSAzMjMgODc3IDQ1MCA1MjMgNTMgNzg4IDcxNiAzMzAgNjk3IDU4MyA1MSA2NjcgOTc0IDM1NSA4MTUgNjM4IDE2IDU5MiA0MjIgNjcgNjA2IDM4NCA0MDQgNTU2IDg0IDk5MiAxNzMgMjY2IDgzNCA0OTAgOTYzIDMxNSAxIDU0OSAzNzMgNzA3IDEyNyA3NDcgNDc3IDIxOSA4MjcgNjQ3IDk1IDggNDE3IDM1NCA5OTcgNDY1IDQ2MyAxNzggOTIxIDgzMCA5MDAgODc0IDMwMiA3OTUgMTMzIDQ5MiA4MzggNDM3IDkzOCAzMzUgNTkgNDczIDg0NiA5ODEgNjM0IDI3OSA4NjUgMTExIDQzMCA0NjcgMTgxIDYyNiA5ODQgMTg1IDQ3MSA2MTYgMjQ2IDI3OCA2MzEgOTMyIDkwNSA4MjYgNjg0IDg5NCAzMjIgNjU3IDcwNiAxNzIgNzIgOTQyIDI3MyA0OTcgMTc5IDEzOCA0MTUgOTY2IDQ0MiAxNzUgMjI3IDIxOSA2ODkgMzcxIDQwMSA4MCA4NTEgODc5IDg1MSA1MjYgNDU5IDg0OSA4NjAgOTI3IDM1NyAxMDAgNTkwIDQxOCAyOTcgNTQzIDM4NiA3MzMgODQ1IDc0NSA5MDQgMjIyIDQ0NSA5NjEgNTE3IDY5NyA3NjQgMjgzIDk3MCA5MzEgMjAxIDgwMSA4NzkgMzE3IDQ1OSA3MDggOTMxIDU0MCAzODYgNzY0IDE4MiAxMzggMjUgNTI0IDM1NiA1MzkgMTU0IDQwOCA0ODQgOTA1IDE1MSA2MjAgNjAxIDI3MiAyMzEgNjcgNjIyIDUwNyA3NTAgNDcwIDQ0MCAyNDkgODc1IDgwMCAxMzIgOTgyIDgwMSA3MTUgMzkyIDY4MiA1NzkgMzYzIDk2MyA5MjggNDQ3IDI4MCAyOSA3MzAgODg5IDkzIDc2NSA3MCA0NzQgNTc1IDcxNiA0NzggNTE3IDQ5NiAzNCA2NCA3NCAxNTQgMzA5IDk2MCA2NzAgNTg1IDQ3MyA0ODIgMjIwIDIyOSA2MjYgOTEzIDk0MyA5NSAyOSA1MTMgNjAzIDQ4MCA3NTMgOTY3IDM2NCAxNDEgODIxIDI4NiAyNDEgMzkzIDQ4MCAzODggODgxIDc1NSA0NDYgNjE2IDU3MSA3ODMgNjQzIDk3NiA5MSAxNzcgNjA4IDI3NCA0NjAgMzIgNDYzIDU3OSAzMzkgOTEwIDY3OCAxNzggMTAxIDk4MyAyMjMgNzczIDkxNCA0MTUgMTIxIDE3MCA0NTUgMTkzIDYyNiA5NCA2MzQgNjQ2IDM5MyA4MDkgNzcgNTYzIDQ2NyAyMTMgNjIgMzEgMjYwIDg4OCA4MSA1NCA3NzEgMzQgMzI3IDY5NCAxMDIgNjkgNDQ1IDQ2MyA4MjIgNTk5IDI2IDcxIDc2MiAyMCAyMjggMTM0IDQgNDcwIDE0NyAyODEgNjQ5IDc3NSA5NjUgNTk5IDU5MyA0NTAgNjM0IDM1OSAxNjAgODg1IDkwNiA5MzggOTMwIDY1MyA3MjMgNDgxIDY1NCA3NzEgOTEzIDc2MSAyMzUgNjI2IDcyMyA0MTggMTYxIDQ4MiAxMjIgNjEyIDg1IDM4MCAyMTIgMjUxIDgxNyAyMTkgMzI2IDcyOCA0MzAgMTYyIDg0OSAyNDggNTkyIDIgNDc0IDU4MCAyMzQgMjg1IDY0NSA4NjYgODc2IDI5OSA3NTcgNDUwIDM0MCA4OSAzMDUgMzA3IDcwNSAyMTAgMjg2IDYyOCAxMTcgNjQgNjg1IDk1NCAzNTcgNTM2IDk3NCA0NzQgMjc5IDUyNiA3MzUgNzkxIDcxMyA0MDYgMTAwMCAxNjQgNDc1IDQyNCA1ODEgMzExIDgxMyAxMTEgMzAgOTQzIDY0MyA1ODYgODM0IDYyNyA5NDEgNTcyIDYzOSA3ODEgNTk2IDUxMyA5MjYgOTU3IDIgMzAzIDkzMiAyOTcgODY4IDIyIDI1NyA4MjQgODgyIDM0OSA5NzAgMTE4IDExNiA4NjIgMjA3IDQxMiAyNTcgOTM0IDQ4OSAyNjIgODU4IDM5MyA5NzQgNjE1IDU4MSA2MDEgMjc3IDcxMSA2MzMgOTU0IDExOCAzOTYgMTUxIDc5MyAxNTIgOTc5IDg3OSA4NiAxMDkgNjgyIDQ5NSAxNTMgNTc2IDg1OSAxNDkgMzA0IDIwOSA0OTkgODUzIDU5NSA2MDYgNDIgODAgOTU0IDQ1OSAyNjIgNDM4IDk2MSAyOTQgNDI5IDY2NSAxODEgNDc2IDg3NiA1NyA0MjMgNzY4IDE5MiA3MDEgNjU4IDIyOCA1OTEgNjkgNzA5IDU1IDU3IDk2IDk5NyA0NjQgMzc3IDI3NiAyMDMgNzI5IDE3MiAzNzkgMjcwIDQ1MSA1ODkgNzkzIDczOSA3NjUgMTMzIDI0NSA0MTYgNzM5IDQ2NSAyMDIgNDk5IDk4MiAxNTEgMjMgOTQwIDQ3NSA4OTkgMzE4IDU5OCA3MjcgOTQ3IDY0MyA0NzggODg5IDk1NyA1NzUgNDE4IDU0NSA5MDQgOTk4IDk2MCAyMjYgOTQwIDI2MiA5NDkgMTg3IDkyMSA3NjEgODkyIDM5MyAxOTUgNTE3IDQ1MyA4NyA3OTcgNjAzIDkwOSA4NDkgMzEyIDIwMCA0NTYgOTI0IDU5MiA2NzMgNTY3IDg0NyAyNzYgMzcyIDMxOSA1MDQgOTgzIDYwOSA4MTcgNjggNTQ3IDU1MyA5MTAgNDA1IDg0NCAzNzIgMjMyIDI3NyAxMzQgMjk3IDk4MiAzMTAgNDk5IDUwMSA5MDIgODU3IDExNiA2MTMgMzQxIDc4MCA3MDQgMjM0IDkwIDE4NiAyMjYgNDMwIDQ1NSA3NTcgNjk0IDY3MSA3MTIgODAyIDgzMiA4MSA3NTcgNDEwIDc2MyA4OTYgNDgzIDIxMyA2OTcgOTQ4IDE0MCA2NDEgODMxIDg5MSA3OTMgODU4IDkwOSA2NzEgOTg5IDU1NyA1MiA4ODAgMzkxIDUwMyA4NTcgMTkgNzA5IDI3MSAzMDMgNDI3IDk0NiAxMjYgODYxIDg2Ng==

1000 100000
33 709 850 724 326 312 200 538 670 176 142 961 44 266 295 605 5 827 110 707 565 239 997 917 283 165 574 83 266 516 936 503 373 157 824 434 597 887 435 212 787 984 821 21 516 689 216 906 896 652 389 715 401 565 330 12 468 861 188 307 193 589 982 34 623 384 126 633 665 762 463 998 134 445 820 371 764 299 365 95 603 980 236 951 293 813 465 35 101 916 245 534 956 280 134 997 657 530 356 403 834 390 969 396 915 689 636 236 743 831 806 1 567 818 708 115 455 617 445 242 960 350 918 405 407 853 824 897 466 886 414 801 387 395 964 953 532 320 548 399 334 394 202 29 139 812 365 19 656 572 346 350 239 853 109 467 851 49 624 352 858 676 854 841 19 16 486 139 145 769 379 840 295 613 938 41 202 596 156 179 621 555 115 814 648 648 460 649 593 812 926 803 78 356 885 877 976 280 141 672 391 313 846 434 225 673 674 298 390 880 36 814 6 186 545 338 503 573 173 688 457 367 926 530 360 15 545 470 61 718 665 877 399 721 49 28 223 846 609 657 488 728 651 941 40 160 673 93 351 109 224 263 37 839 711 439 232 380 466 961 718 239 327 529 782 487 680 744 756 275 701 530 814 579 721 30 381 876 263 628 9 150 68 902 88 148 268 448 346 363 473 389 983 195 437 554 345 283 737 747 745 43 163 456 589 546 477 732 828 34 270 669 148 233 653 292 306 315 28 709 859 39 349 290 501 521 688 767 72 855 777 422 392 941 713 935 954 243 302 89 914 918 528 853 141 826 809 695 455 832 313 387 839 11 731 383 834 773 797 671 66 119 38 406 843 361 21 98 540 21 700 820 451 316 444 115 906 715 24 121 948 477 676 633 672 897 653 535 5 427 248 331 658 3 326 705 55 339 960 465 428 29 432 328 455 94 613 435 573 331 560 902 495 936 257 757 928 17 55 967 626 583 253 657 921 410 786 932 727 494 615 174 719 193 553 588 325 544 422 103 982 399 876 445 407 146 152 1 926 932 707 357 717 540 918 740 406 911 168 84 308 865 523 319 168 403 573 843 395 222 420 934 28 451 364 88 356 578 794 44 837 419 943 887 765 459 19 89 594 763 263 377 559 589 395 191 553 253 605 23 815 798 319 859 156 574 34 70 860 433 603 600 88 423 419 431 856 915 549 519 50 446 564 376 215 852 3 383 613 438 734 458 156 689 105 724 842 508 83 382 715 255 813 998 599 812 492 653 398 351 536 832 334 753 438 788 360 81 840 434 523 44 677 738 111 866 142 30 238 321 946 851 649 789 877 602 381 630 601 193 272 489 71 966 236 995 801 366 776 961 846 79 668 423 569 128 252 724 830 310 484 327 831 932 711 660 561 599 786 69 198 931 860 892 934 79 774 279 271 894 894 187 250 266 390 296 637 848 204 842 696 626 103 887 148 739 41 560 942 955 2 777 721 121 270 338 492 666 464 160 18 128 27 368 818 370 431 20 621 926 454 867 11 819 827 664 966 15 625 58 870 749 414 60 558 966 592 261 82 169 54 636 500 750 746 268 30 619 326 78 891 499 655 571 645 935 965 494 968 777 946 80 439 611 628 127 428 470 105 833 991 587 429 291 47 890 373 72 543 513 774 845 700 256 681 400 418 16 171 230 863 602 366 405 710 829 954 591 263 776 626 192 139 261 540 147 957 684 370 975 455 262 757 236 369 101 44 604 328 727 214 216 904 110 899 967 937 61 816 795 211 534 34 959 941 288 490 509 164 870 668 745 552 255 446 141 694 570 508 162 264 228 571 484 10 698 570 937 539 942 352 203 989 575 648 152 54 996 873 783 547 213 233 263 797 296 391 307 177 940 729 18 793 759 352 617 446 871 621 661 157 769 867 281 518 468 330 37 435 778 345 550 493 77 616 934 633 449 104 200 240 732 699 743 293 363 385 990 892 503 538 2 557 327 329 319 504 507 489 435 518 290 451 443 745 721 80 670 517 824 342 861 281 897 155 840 99 559 222 40 930 706 510 987 30 448 330 915 523 753 610 1 290 68 832 173 978 220 667 997 924 68 692 344 374 656 720 127 240 458 679 632 711 901 650 280 460 380 128 106 664 751 869 298 238 871 843 974 406 771 648 427 913 503 682 134 122 992 504 358 787 342 240 536 226 813 46 385 981 426 230 932 334 618 11 698 198 480 730 750 477 395 814 204 193 934 913 395 454 928 431 255 964 42 42 773 498 853 607 540 736 460 870 351 611 530 474 264 768 777
805 231 946 765 349 576 267 857 746 147 138 634 383 643 895 355 932 273 247 563 905 974 550 669 389 213 897 581 902 373 196 464 109 65 216 602 540 479 790 890 45 169 582 744 984 54 611 752 22 256 74 322 746 150 112 698 56 413 549 328 822 154 593 544 73 678 322 990 948 868 950 415 280 563 344 740 556 439 199 288 992 157 675 6 151 616 461 864 177 762 240 313 640 854 641 891 895 88 984 445 454 758 263 314 9 995 271 192 159 825 293 43 602 492 672 327 640 593 826 382 7 711 265 40 516 817 49 316 609 849 424 521 424 823 522 868 132 700 162 146 53 626 851 525 473 500 250 440 446 602 550 179 882 490 916 527 120 667 152 582 533 273 62 955 980 671 512 28 114 221 556 990 61 462 822 728 616 537 75 321 783 35 457 548 601 458 348 856 479 13 624 344 866 271 133 197 347 68 687 833 380 591 652 330 645 468 944 690 781 100 279 137 393 989 310 1 967 237 990 997 177 2 948 293 470 844 264 947 457 666 898 634 490 399 665 393 855 849 918 502 531 414 455 534 578 132 420 692 957 994 521 159 166 364 795 954 133 519 767 61 287 731 394 840 413 250 717 347 629 348 472 379 264 858 660 506 62 653 964 491 461 139 593 897 288 721 108 773 393 726 132 877 211 274 510 452 500 518 593 391 740 407 182 928 32 401 62 720 852 327 512 626 429 84 489 810 290 551 156 25 701 24 860 596 217 589 682 72 240 673 180 796 832 828 850 122 269 372 544 43 940 276 543 261 813 18 54 788 135 65 119 781 568 472 717 171 333 889 48 150 259 322 729 23 911 73 652 924 109 510 706 501 892 379 100 454 378 545 106 705 847 171 756 776 851 575 269 451 269 372 888 856 972 87 195 856 592 571 571 323 877 450 523 53 788 716 330 697 583 51 667 974 355 815 638 16 592 422 67 606 384 404 556 84 992 173 266 834 490 963 315 1 549 373 707 127 747 477 219 827 647 95 8 417 354 997 465 463 178 921 830 900 874 302 795 133 492 838 437 938 335 59 473 846 981 634 279 865 111 430 467 181 626 984 185 471 616 246 278 631 932 905 826 684 894 322 657 706 172 72 942 273 497 179 138 415 966 442 175 227 219 689 371 401 80 851 879 851 526 459 849 860 927 357 100 590 418 297 543 386 733 845 745 904 222 445 961 517 697 764 283 970 931 201 801 879 317 459 708 931 540 386 764 182 138 25 524 356 539 154 408 484 905 151 620 601 272 231 67 622 507 750 470 440 249 875 800 132 982 801 715 392 682 579 363 963 928 447 280 29 730 889 93 765 70 474 575 716 478 517 496 34 64 74 154 309 960 670 585 473 482 220 229 626 913 943 95 29 513 603 480 753 967 364 141 821 286 241 393 480 388 881 755 446 616 571 783 643 976 91 177 608 274 460 32 463 579 339 910 678 178 101 983 223 773 914 415 121 170 455 193 626 94 634 646 393 809 77 563 467 213 62 31 260 888 81 54 771 34 327 694 102 69 445 463 822 599 26 71 762 20 228 134 4 470 147 281 649 775 965 599 593 450 634 359 160 885 906 938 930 653 723 481 654 771 913 761 235 626 723 418 161 482 122 612 85 380 212 251 817 219 326 728 430 162 849 248 592 2 474 580 234 285 645 866 876 299 757 450 340 89 305 307 705 210 286 628 117 64 685 954 357 536 974 474 279 526 735 791 713 406 1000 164 475 424 581 311 813 111 30 943 643 586 834 627 941 572 639 781 596 513 926 957 2 303 932 297 868 22 257 824 882 349 970 118 116 862 207 412 257 934 489 262 858 393 974 615 581 601 277 711 633 954 118 396 151 793 152 979 879 86 109 682 495 153 576 859 149 304 209 499 853 595 606 42 80 954 459 262 438 961 294 429 665 181 476 876 57 423 768 192 701 658 228 591 69 709 55 57 96 997 464 377 276 203 729 172 379 270 451 589 793 739 765 133 245 416 739 465 202 499 982 151 23 940 475 899 318 598 727 947 643 478 889 957 575 418 545 904 998 960 226 940 262 949 187 921 761 892 393 195 517 453 87 797 603 909 849 312 200 456 924 592 673 567 847 276 372 319 504 983 609 817 68 547 553 910 405 844 372 232 277 134 297 982 310 499 501 902 857 116 613 341 780 704 234 90 186 226 430 455 757 694 671 712 802 832 81 757 410 763 896 483 213 697 948 140 641 831 891 793 858 909 671 989 557 52 880 391 503 857 19 709 271 303 427 946 126 861 866