#pragma G++ optimize("Ofast")
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp> 
using namespace std;
using namespace __gnu_pbds;

#define fren BIG_OUNCE69420
#define ln "\n"
#define mt make_tuple
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define beg begin
#define all(X) (X).beg(), (X).end()
#define sz(X) ((int)X.size())
#define erase_dupes(X) sort(all(X)); (X).resize(distance((X).beg(), unique(all(X))));
#define setp(X) setPrecision(X)
#define setd(X) setDelimiter(X)
#define mst(X,N,Y) for (int i = 0; i < N; ++i) X[i] = Y;
#define SORT(X) sort(all(X))
#define REV(X) reverse(all(X));
#define CNT(X,Y) count(all(X),Y)
#define mayn main

///// TYPES /////
typedef long long LL; 
typedef double DBL; typedef pair<int,int> PII; 
typedef pair<LL,LL> PLL; typedef pair<string, int> PSI;
typedef pair<int,string> PIS; typedef vector<PSI> VPSI;
typedef vector<PIS> VPIS; typedef pair<char,int> PCI;
typedef pair<int,char> PIC; typedef vector<PCI> VPCI;
typedef vector<PIC> VPIC; typedef vector<PII> VPII;
typedef vector<PLL> VPLL; typedef vector<LL> VLL;
typedef vector<int> VI; typedef vector<string> VS;
typedef vector<char> VC; typedef long double LD;
typedef pair<LD,LD> PLD; typedef vector<LD> VLD;
typedef vector<PLD> VPLD; typedef vector< VI > VVI;
typedef vector< VLL > VVLL; typedef void voyd;
///// END OF TYPES /////

///// CLOCK /////
std::seed_seq seq{
    (uint64_t)std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::steady_clock::now().time_since_epoch()).count(),
    (uint64_t)__builtin_ia32_rdtsc(),(uint64_t)(uintptr_t)make_unique<char>().get()
};
std::mt19937 rng(seq); std::mt19937_64 rng64(seq);
mt19937 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
auto clk=clock();
///// END OF CLOCK /////

const int MOD = 1e9+7;
template<class T> void addmod(T &a, const T &b) {a=(a+b)%MOD;if(a<0)a+=MOD;}
template<class T> void submod(T &a, const T &b) {a=(a-b)%MOD;if(a<0)a+=MOD;}
template<class T> void multmod(T &a, const T &b) {a=(a*b)%MOD;}
template<class T> void amax(T &a, const T &b) {if(b>a)a=b;}
template<class T> void amin(T &a, const T &b) {if(b<a)a=b;}
template<typename T> T gcd(T a, T b) {return b?gcd(b,a%b):a;}
template<typename T> T sqr(T x) {return x*x;}
const std::size_t RANDOM=std::uniform_int_distribution<std::size_t>(0,std::numeric_limits<std::size_t>::max())(rng64);

///// CONTAINERS /////
template<class T,class H=std::hash<T>>struct rand_hash{
    static uint64_t splitmix64(uint64_t x){x+=0x9e3779b97f4a7c15;x=(x^(x>>30))*0xbf58476d1ce4e5b9;x=(x^(x>>27))*0x94d049bb133111eb;return x^(x>>31);}
    std::size_t operator()(const T&x)const{return splitmix64(H{}(x)+RANDOM);}
};
template<class K,class C=std::less<K>,class...Ts>using oset=__gnu_pbds::tree<K,__gnu_pbds::null_type,C,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update,Ts...>;
template<class K,class V,class C=std::less<K>,class...Ts>using treemap=__gnu_pbds::tree<K,V,C,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update,Ts...>;
template<class K,class H=rand_hash<K>,class...Ts>using uset=std::unordered_set<K,H,Ts...>;
template<class K,class V,class H=rand_hash<K>,class...Ts>using umap=unordered_map<K,V,H,Ts...>;
template<class T>using minpq=std::priority_queue<T,std::vector<T>,std::greater<T>>;
template<class T>using maxpq=std::priority_queue<T,std::vector<T>,std::less<T>>;
template<class T>using minpairingheap=__gnu_pbds::priority_queue<T,std::greater<T>,__gnu_pbds::pairing_heap_tag>;
template<class T>using maxpairingheap=__gnu_pbds::priority_queue<T,std::less<T>,__gnu_pbds::pairing_heap_tag>;
///// END OF CONTAINERS /////

///// DEBUGGING /////
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const deque<T> &vec){ os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const uset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa){ os << "(" << pa.ff << "," << pa.ss << ")"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mpi){ os << "{"; for (auto v : mpi) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const umap<TK, TV> &mpi){ os << "{"; for (auto v : mpi) os << v.first << "=>" << v.second << ","; os << "}"; return os; }

template<class TH> void _dbg(const char *sdbg, TH h) {cerr<<sdbg<<" = "<<h<<endl;}
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',') cerr<<*sdbg++;
  cerr<<" = "<<h<<", "; _dbg(sdbg+1, a...);
}

#define LOCAL
#define SEPERATOR cout << "-----------------------------------------" << endl;

#ifdef LOCAL
	#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
	#define dbg(...)
	#define cerr if(0)cout
#endif
///// END OF DEBUGGING /////

///// I/O /////
template <class T> struct is_iterator {
  template <class U, typename enable_if<!is_convertible<U, const char*>::value, int>::type = 0>
  constexpr static auto has_indirection(int) -> decltype(*declval<U>(), bool()) { return true; }
  template <class> constexpr static bool has_indirection(long) { return false; }
  constexpr static bool value = has_indirection<T>(0);
};
using uint = unsigned int;
const uint BUFFER_SIZE = 1 << 12;
const uint MAX_LENGTH = 1 << 7;
namespace Detail {
  struct Width { uint value; };
  struct Fill { char value; };
  struct Base { uint value; };
  struct Precision { uint value; };
  struct Delimiter { const char* value; };
}
Detail::Width setWidth(uint value = 0) { return {value}; }
Detail::Fill setFill(char value = ' ') { return {value}; }
Detail::Base setBase(uint value = 10) { assert(2 <= value && value <= 36); return {value}; }
Detail::Precision setPrecision(uint value = 9) { assert(value < MAX_LENGTH); return {value}; }
Detail::Delimiter setDelimiter(const char* value = " ") { return {value}; }
class InputDevice {
protected:
  const char* head;
  const char* tail;
  InputDevice(const char* head, const char* tail) : head(head), tail(tail), base(setBase().value) {}
  virtual void fillInput() = 0;
  inline char nextChar() {
    if (__builtin_expect(head >= tail, false)) fillInput();
    return *head++;
  }
  template <class I> int readUnsignedIntGeneral(I& arg, char c) {
    I value = 0;
    int length = 0;
    for (;; ++length, c = nextChar()) {
      if (isDigit(c)) c -= '0';
      else if (isUpper(c)) c -= 'A' - 10;
      else if (isLower(c)) c -= 'a' - 10;
      else c = base;
      if (c >= base) break;
      value = base * value + c;
    }
    arg = value;
    return --head, length;
  }
  template <class I> inline int readUnsignedInt(I& arg, char c) {
    if (__builtin_expect(base > 10, false)) return readUnsignedIntGeneral(arg, c);
    I value = 0;
    int length = 0;
    for (; static_cast<unsigned char>(c - '0') < base; ++length, c = nextChar())
      value = base * value + c - '0';
    arg = value;
    return --head, length;
  }
  template <class I> inline bool readSignedInt(I& arg, char c) {
    bool negative = c == '-';
    if (negative) c = nextChar();
    typename make_unsigned<I>::type unsignedArg;
    if (readUnsignedInt(unsignedArg, c) == 0) return false;
    arg = negative ? ~static_cast<I>(unsignedArg - 1) : static_cast<I>(unsignedArg);
    return true;
  }
  template <class F> bool readFloatingPoint(F& arg, char c) {
    bool negative = c == '-';
    if (negative) c = nextChar();
    unsigned long long integerPart;
    if (readUnsignedInt(integerPart, c) == 0) return false;
    arg = static_cast<F>(integerPart);
    if (nextChar() == '.') {
      unsigned long long fractionalPart = 0;
      int fractionalLength = readUnsignedInt(fractionalPart, nextChar());
      if (fractionalLength > 0) {
        unsigned long long basePower = 1;
        for (; fractionalLength; --fractionalLength) basePower *= base;
        arg += static_cast<F>(fractionalPart) / basePower;
      }
    } else --head;
    if (negative) arg = -arg;
    return true;
  }
public:
  uint base;
  InputDevice(InputDevice const&) = delete;
  InputDevice& operator = (InputDevice const&) = delete;
  static inline bool isSpace(char c) { return static_cast<unsigned char>(c - '\t') < 5 || c == ' '; }
  static inline bool isDigit(char c) { return static_cast<unsigned char>(c - '0') < 10; }
  static inline bool isUpper(char c) { return static_cast<unsigned char>(c - 'A') < 26; }
  static inline bool isLower(char c) { return static_cast<unsigned char>(c - 'a') < 26; }
  static inline bool isOneOf(char c, const char* str) { return strchr(str, c) != nullptr; }
  void putBack() { --head; } inline bool readChar(char& arg) {
  if (__builtin_expect(head >= tail, false)) {fillInput();
  if (__builtin_expect(head >= tail, false)) return arg = '\0', false;}return arg = *head++, true;}
  template <class UnaryPredicate>inline char skipCharacters(UnaryPredicate isSkipped) {
    char c;do { c = nextChar(); } while (isSkipped(c));return c;}
  inline char skipCharacters() { return skipCharacters(isSpace); }
  template <class UnaryPredicate>inline int readString(char* arg, int limit, UnaryPredicate isTerminator) {
    skipCharacters(isTerminator);
    int charsRead = 0;
    for (--head, --limit; head < tail; fillInput()) {
      ptrdiff_t chunkSize = find_if(head, min(tail, head + limit - charsRead), isTerminator) - head;
      arg = copy_n(head, chunkSize, arg);
      head += chunkSize;
      charsRead += chunkSize;
  if (chunkSize == 0 || head < tail) break;}return *arg = '\0', charsRead;}
  inline int readString(char* arg, int limit, const char* terminators) {
  if (!*terminators) return readString(arg, limit, InputDevice::isSpace);return readString(arg, limit, [terminators](char c) { return InputDevice::isOneOf(c, terminators); });}
  inline bool read(Detail::Base newBase) { base = newBase.value; return true; }inline bool read() { return true; }
  inline bool read(char& arg) { return readChar(arg); }
  template <class I> inline typename enable_if<is_integral<I>::value && is_unsigned<I>::value,
  bool>::type read(I& arg) { return readUnsignedInt(arg, skipCharacters()) > 0; }
  template <class I> inline typename enable_if<is_integral<I>::value && is_signed<I>::value,
  bool>::type read(I& arg) { return readSignedInt(arg, skipCharacters()); }
  template <class F> inline typename enable_if<is_floating_point<F>::value,
  bool>::type read(F& arg) { return readFloatingPoint(arg, skipCharacters()); }
  inline bool read(const char& arg) { skipCharacters([arg](char c) { return arg != c; }); return true; }
  inline bool read(const char* arg) {if (*arg) skipCharacters([arg](char c) { return InputDevice::isOneOf(c, arg); });
  else skipCharacters();return putBack(), true;}
  inline bool read(bool (*isSkipped)(char)) { skipCharacters(isSkipped); putBack(); return true; }
  template <class I, class Terminator, class... Ts> inline typename enable_if<is_integral<I>::value,
  bool>::type read(char* arg, I limit, Terminator terminator, Ts&&... args) {readString(arg, static_cast<int>(limit), terminator);return read(forward<Ts>(args)...);}
  template <class I> inline typename enable_if<is_integral<I>::value,bool>::type read(char* arg, I limit) { return read(arg, limit, ""); }
  template <class... Ts>inline bool read(char* first, char* last, Ts&&... args) {return read(first, static_cast<int>(last - first), forward<Ts>(args)...);}
  template <int N, class... Ts>
  inline bool read(char (&arg)[N], Ts&&... args) { return read(static_cast<char*>(arg), N, forward<Ts>(args)...); }
  template <class Terminator, class... Ts>
  inline bool read(string& arg, Terminator terminator, Ts&&... args) {
    for (int length = 16, last = 0;; last += length, length <<= 1) {
      arg.resize(last + length);
      int charsRead = readString(&arg[last], length + 1, terminator);
      if (charsRead < length) {
        arg.resize(last + charsRead);
        return read(forward<Ts>(args)...);
      }
    }
  }
  inline bool read(string& arg) { return read(arg, ""); }
  template <class T1, class T2>inline bool read(pair<T1, T2>& arg) { return read(arg.first, arg.second); }
  template <class T>inline bool read(complex<T>& arg) {
  T real, imag;if (!read(real, imag)) return false;arg.real(real), arg.imag(imag);return true;}
  template <class T>inline bool read(vector<T>& arg) {
  uint n;if (!read(n)) return false;arg.resize(n);return read(arg.begin(), arg.end());}
  template <class Iterator, class... Ts> inline typename enable_if<is_iterator<Iterator>::value,
  bool>::type read(Iterator first, Iterator last, Ts&&... args) {for (; first != last; ++first) if (!read(*first)) return false;return read(forward<Ts>(args)...);}
  template <class Iterator, class I, class... Ts>inline typename enable_if<is_iterator<Iterator>::value && is_integral<I>::value,
  bool>::type read(Iterator first, I count, Ts&&... args) { return read(first, first + count, forward<Ts>(args)...); }
  template <class T>inline auto read(T& arg) -> decltype(arg.read(*this)) { return arg.read(*this); }
  template <class T0, class T1, class... Ts>inline typename enable_if<!is_iterator<T0>::value && !is_convertible<T0, char*>::value,
  bool>::type read(T0&& arg0, T1&& arg1, Ts&&... args) {return read(forward<T0>(arg0)) && read(forward<T1>(arg1), forward<Ts>(args)...);}
};
class InputFile : public InputDevice {
  FILE* file;bool lineBuffered;bool owner;char buffer[BUFFER_SIZE];
  void fillInput() override {head = buffer;*buffer = '\0';
  if (__builtin_expect(!lineBuffered, true)) {tail = head + fread(buffer, 1, BUFFER_SIZE, file);}
  else {tail = head;if (fgets(buffer, BUFFER_SIZE, file)) while (*tail) ++tail;}}
public:
  InputFile(FILE* file = stdin, bool lineBuffered = true, bool takeOwnership = false)
  : InputDevice(buffer, buffer) , file(file), lineBuffered(lineBuffered), owner(takeOwnership) {}
  InputFile(const char* fileName) : InputFile(fopen(fileName, "r"), false, true) {}
  ~InputFile() { if (owner) fclose(file); }
};
class InputString : public InputDevice {
  void fillInput() override { while (*tail) ++tail; }
public:
  InputString(const string& s) : InputDevice(s.data(), s.data() + s.size()) {}
  InputString(const char* s) : InputDevice(s, s + strlen(s)) {}
};
class OutputDevice {
protected:
  char buffer[BUFFER_SIZE + MAX_LENGTH];char* output;char* end;bool separate;
  OutputDevice() : output(buffer), end(buffer + BUFFER_SIZE + MAX_LENGTH), separate(false)
  , width(setWidth().value), fill(setFill().value), base(setBase().value), precision(setPrecision().value)
  , delimiter(setDelimiter().value) { computeBasePower(); }virtual void writeToDevice(uint count) = 0;
  inline void flushMaybe() {if (__builtin_expect(output >= buffer + BUFFER_SIZE, false)) {
   writeToDevice(BUFFER_SIZE);output = copy(buffer + BUFFER_SIZE, output, buffer);}}
  void computeBasePower() {basePower = 1;for (uint i = 0; i < precision; ++i) basePower *= base;}
  template <class I> inline char* writeUnsignedInt(I arg, char* last) {if (__builtin_expect(arg == 0, false)) *--last = '0';
  if (__builtin_expect(base == 10, true)) {for (; arg; arg /= 10) *--last = '0' + arg % 10;}else for (; arg; arg /= base) {
  I digit = arg % base;*--last = digit < 10 ? '0' + digit : 'A' - 10 + digit;}return last;}
  template <class I> inline char* writeSignedInt(I arg, char* last) {auto unsignedArg = static_cast<typename make_unsigned<I>::type>(arg);
  if (arg < 0) {last = writeUnsignedInt(~unsignedArg + 1, last);*--last = '-';return last;}return writeUnsignedInt(unsignedArg, last);}
  template <class F> char* writeFloatingPoint(F arg, char* last) {bool negative = signbit(arg);if (negative) arg = -arg;
  if (isnan(arg)) for (int i = 0; i < 3; ++i) *--last = i["NaN"];else if (isinf(arg)) for (int i = 0; i < 3; ++i) *--last = i["fnI"];
  else {auto integerPart = static_cast<unsigned long long>(arg);
  auto fractionalPart = static_cast<unsigned long long>((arg - integerPart) * basePower + F(0.5));
  if (fractionalPart >= basePower) ++integerPart, fractionalPart = 0;char* point = last - precision;
  if (precision > 0) {::fill(point, writeUnsignedInt(fractionalPart, last), '0');*--point = '.';}
  last = writeUnsignedInt(integerPart, point);}if (negative) *--last = '-';return last;}
  inline int writeT(char* first) {int delimiterLenght = separate ? writeDelimiter() : 0;
  separate = true;uint charsWritten = static_cast<uint>(end - first);
  if (__builtin_expect(charsWritten < width, false))charsWritten += writeFill(width - charsWritten);
  output = copy(first, end, output);flushMaybe();return delimiterLenght + static_cast<int>(charsWritten);}
  inline int writeFill(uint count) {int charsWritten = static_cast<int>(count);
  if (__builtin_expect(output + count + MAX_LENGTH < end, true)) {
  if (count == 1) *output++ = fill;else output = fill_n(output, count, fill);}
  else for (uint chunkSize = static_cast<uint>(buffer + BUFFER_SIZE - output);; chunkSize = BUFFER_SIZE) {
  if (chunkSize > count) chunkSize = count;
  output = fill_n(output, chunkSize, fill);flushMaybe();if ((count -= chunkSize) == 0) break;}return charsWritten;}
public:
  uint width;char fill;
  uint base;uint precision;unsigned long long basePower;string delimiter;
  OutputDevice(OutputDevice const&) = delete;
  OutputDevice& operator = (OutputDevice const&) = delete;
  virtual ~OutputDevice() {};inline int writeChar(char arg) { separate = false; *output++ = arg; flushMaybe(); return 1; }
  inline int writeString(const char* arg, size_t length, bool checkWidth = true) {
  separate = false;uint count = static_cast<uint>(length);
  int charsWritten = static_cast<int>(count) + (checkWidth && count < width ? writeFill(width - count) : 0);
  if (__builtin_expect(output + count + MAX_LENGTH < end, true)) {
  if (count == 1) *output++ = *arg;else output = copy_n(arg, count, output);}
  else for (uint chunkSize = static_cast<uint>(buffer + BUFFER_SIZE - output);; chunkSize = BUFFER_SIZE) {
  if (chunkSize > count) chunkSize = count;output = copy_n(arg, chunkSize, output);flushMaybe();
  if ((count -= chunkSize) == 0) {break;}arg += chunkSize;}return charsWritten;}
  inline int writeDelimiter() { return writeString(delimiter.c_str(), delimiter.size(), false); }
  inline void flush() {writeToDevice(static_cast<uint>(output - buffer));output = buffer;}
  inline int write(Detail::Width newWidth) { width = newWidth.value; return 0; }
  inline int write(Detail::Fill newFill) { fill = newFill.value; return 0; }
  inline int write(Detail::Base newBase) { base = newBase.value; computeBasePower(); return 0; }
  inline int write(Detail::Precision newPrecision) {precision = newPrecision.value; computeBasePower(); return 0;}
  inline int write(Detail::Delimiter newDelimiter) { delimiter = newDelimiter.value; return 0; }
  inline int write() { return 0; }inline int write(char arg) { return writeChar(arg); }
  template <class I> inline typename enable_if<is_integral<I>::value && is_unsigned<I>::value,
  int>::type write(I arg) { return writeT(writeUnsignedInt(arg, end)); }
  template <class I> inline typename enable_if<is_integral<I>::value && is_signed<I>::value,
  int>::type write(I arg) { return writeT(writeSignedInt(arg, end)); }
  template <class F> inline typename enable_if<is_floating_point<F>::value,
  int>::type write(F arg) { return writeT(writeFloatingPoint(arg, end)); }
  inline int write(const char* arg) { return writeString(arg, strlen(arg)); }
  template <int N>inline int write(char (&arg)[N]) { return writeString(arg, strlen(arg)); }
  inline int write(const string& arg) { return writeString(arg.c_str(), arg.size()); }
  template <class T1, class T2>inline int write(const pair<T1, T2>& arg) {
  int charsWritten = write(arg.first);charsWritten += writeDelimiter();return charsWritten + write(arg.second);}
  template <class T>inline int write(const complex<T>& arg) { return write(real(arg), imag(arg)); }
  template <class Iterator, class... Ts> inline typename enable_if<is_iterator<Iterator>::value,
  int>::type write(Iterator first, Iterator last, Ts&&... args) {
  int charsWritten = 0;for (; first != last; charsWritten += ++first == last ? 0 : writeDelimiter()) charsWritten += write(*first);
  return charsWritten + write(forward<Ts>(args)...);}
  template <class Iterator, class I, class... Ts> inline typename enable_if<is_iterator<Iterator>::value && is_integral<I>::value,
  int>::type write(Iterator first, I count, Ts&&... args) { return write(first, first + count, forward<Ts>(args)...); }
  template <class T>inline auto write(const T& arg) -> decltype(arg.write(*this)) { return arg.write(*this); }
  template <class T0, class T1, class... Ts> inline typename enable_if<!is_iterator<T0>::value,
  int>::type write(T0&& arg0, T1&& arg1, Ts&&... args) {
    int charsWritten = write(forward<T0>(arg0));
    return charsWritten + write(forward<T1>(arg1), forward<Ts>(args)...);
  }
};
class OutputFile : public OutputDevice {
  FILE* file;bool owner;
  void writeToDevice(uint count) override {fwrite(buffer, 1, count, file);fflush(file);}
public:
  OutputFile(FILE* file = stdout, bool takeOwnership = false) : file(file), owner(takeOwnership) {}
  OutputFile(const char* fileName) : OutputFile(fopen(fileName, "w"), true) {}
  ~OutputFile() override { flush(); if (owner) fclose(file); }
};
class OutputString : public OutputDevice {
  string& str;void writeToDevice(uint count) override { str.append(buffer, count); }
public:
  OutputString(string& str) : OutputDevice(), str(str) {}
  ~OutputString() override { flush(); }
};
unique_ptr<InputDevice> input; unique_ptr<OutputDevice> output;
template <class... Ts> inline bool read(Ts&&... args) { return input->read(forward<Ts>(args)...); }
template <class... Ts> inline int write(Ts&&... args) { return output->write(forward<Ts>(args)...); }
template <class... Ts> inline int writeln(Ts&&... args) { return write(forward<Ts>(args)..., '\n'); }
void flush() { output->flush(); }
/********************************I/O INFO/PARAMETERES*******************************************
 * Read returns true if all the arguments were successfully read. Parameters:
 * - setBase(uint): base for integer and floating point numbers
 * Single variable of one of the following types:
 * - char, standard integer and floating point types
 * - pair, complex
 * - vector (size and then the elements)
 * Characters skip:
 * - char: skip until the given character is encountered and read it
 * - const char*: skip all the characters from the string
 * - predicate: skip all the characters satisfying the predicate
 * Strings: read until character limit is reached or termination character is found
 *   (one of the characters in a given string or defined by predicate, isspace by default)
 * - char (&)[N], terminator
 * - char*, int limit, terminator
 * - string&, terminator
 * Ranges:
 * - Iterator first, Iterator last
 * - Iterator first, int count
 **************************************************************************************
 * Write returns number of characters written. Parameters:
 * - setWidth(uint): minimum width of a single element to write (except character)
 * - setFill(char): character prepended to an element until set width is reached
 * - setBase(uint): base for integer and floating point numbers
 * - setPrecision(uint): number of digits after the decimal point
 * - setDelimiter(const char*): delimiter automatically inserted between elements
 *   that are not strings or characters
 * Single variable of one of the following types:
 * - char, standard integer and floating point types
 * - string, const char*
 * - pair, complex
 * Ranges:
 * - Iterator first, Iterator last
 * - Iterator first, int count
***********************************************************************************************/
///// END OF I/O /////

const int maxn = 1e5+7;
const int inf = 1e9+7;
const LL LLinf = ((LL)1e18)+7LL;
const DBL pi = acos(-1.0);

//#define CLOCK
// **************************************** NICE **************************************** //

int n, W;
LL memo[101][maxn];
bool check[101][maxn];
VI w(101), v(101);

LL dp(int i, int C) {
	if (i < 0) return 0;
	if (C < w[i]) return dp(i-1,C);
	if (check[i][C]) return memo[i][C];
	
	LL choose, skip;
	choose = dp(i-1,C-w[i]) + v[i];
	skip = dp(i-1,C);
	
	check[i][C] = 1;
	memo[i][C] = max(choose,skip);
	
	return max(choose,skip);
}

void slov() {
	input.reset(new InputFile());
	output.reset(new OutputFile());
	
	read(n,W); 
	for (int i = 0; i < n; ++i) read(w[i],v[i]);
	
	write(dp(n-1,W));
}

int32_t mayn() {
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	
	slov();
	
	#ifdef CLOCK
		cout << endl;
		SEPERATOR
		cout << "Time elapsed: "<< (DBL)(clock()-clk)/CLOCKS_PER_SEC << endl;
	#endif
}


Measured memory_bytes: 88320