#include <bits/stdc++.h>
bool RANDOM = false;
using namespace std;
double EPS = 0.0000000001;
double INF = 1000000000000000.0;
ostream_iterator<long long int> oi(cout, " ");
long long int minInt = 1;
long long int maxInt = 100;
double minDouble = -100000000000.0;
double maxDouble = 100000000000.0;
void setMaxInt(long long int newMax) { maxInt = newMax; }
void setMinInt(long long int newMin) { minInt = newMin; }
void setIntRange(long long int min, long long int max) {
  maxInt = max;
  minInt = min;
}
void setMaxDouble(double newMax) { maxDouble = newMax; }
void setMinDouble(double newMin) { minDouble = newMin; }
void setDoubleRange(double min, double max) {
  maxDouble = max;
  minDouble = min;
}
ostream& operator<<(ostream& out, pair<long long int, long long int>& c) {
  out << "<" << c.first << ", ";
  out << c.second << ">" << endl;
  return out;
}
void print() { std::cout << endl; }
template <typename A>
void print(A value) {
  std::cout << value;
}
template <typename A, typename B>
void print(A value1, B value2) {
  cout << value1 << " " << value2;
}
template <typename A, typename B, typename C>
void print(A value1, B value2, C value3) {
  cout << value1 << " " << value2 << " " << value3;
}
template <typename A, typename B, typename C, typename D>
void print(A value1, B value2, C value3, D value4) {
  cout << value1 << " " << value2 << " " << value3 << " " << value4;
}
template <typename A>
void println(A value) {
  std::cout << value << endl;
}
template <typename A, typename B>
void println(A value1, B value2) {
  cout << value1 << " " << value2 << endl;
}
template <typename A, typename B, typename C>
void println(A value1, B value2, C value3) {
  cout << value1 << " " << value2 << " " << value3 << endl;
}
template <typename A, typename B, typename C, typename D>
void println(A value1, B value2, C value3, D value4) {
  cout << value1 << " " << value2 << " " << value3 << " " << value4 << endl;
}
long long int randomint(long long int min, long long int max) {
  return rand() % (max - min + 1) + min;
}
double randomdouble(double min, double max) {
  return (rand() / (double)RAND_MAX) * (max - min) + min;
}
template <typename E>
E read() {
  E value;
  cin >> value;
  return value;
}
template <>
long long int read<long long int>() {
  if (!RANDOM) {
    long long int value;
    cin >> value;
    return value;
  } else {
    return randomint(minInt, maxInt);
  }
}
template <>
double read<double>() {
  if (!RANDOM) {
    double value;
    cin >> value;
    return value;
  } else {
    return randomdouble(minDouble, maxDouble);
  }
}
istream& operator>>(istream& in, pair<long long int, long long int>& c) {
  c.first = read<long long int>();
  c.second = read<long long int>();
  return in;
}
ostream& operator<<(ostream& out, string& c) {
  for (long long int i = 0; i < c.length(); i++) {
    putchar(c[i]);
  }
  return out;
}
template <typename E>
class Array {
 public:
  long long int size;
  Array<E>(long long int _capacity) {
    capacity = _capacity;
    array = new E[capacity];
    size = capacity;
    fill();
  }
  void sort() { std::sort(&array[0], &array[size]); }
  Array() {
    capacity = 4;
    array = new E[capacity];
    size = 0;
  }
  Array(vector<E>& vect) {
    long long int _size = vect.size();
    capacity = _size * 2;
    size = _size;
    array = new E[capacity];
    for (long long int i = 0; i < size; i++) {
      array[i] = vect[i];
    }
  }
  Array(long long int minBound, long long int maxBound, long long int _size) {
    srand(_size);
    capacity = _size * 2;
    size = _size;
    array = new E[capacity];
    for (long long int i = 0; i < size; i++) {
      array[i] = randomint(minBound, maxBound);
    }
  }
  void add(E item);
  long long int leftBinarySearch(E& item);
  long long int rightBinarySearch(E& item);
  pair<long long int, long long int> equalRange(E& item);
  bool binarySearch(E& item);
  void fill();
  E* begin();
  E* end();
  vector<E> toVector();
  void toString(ostream& stream);
  E& operator[](long long int i);
  E& index(long long int i);
  E* array;

 private:
  long long int capacity;
  void ensureCapacity(long long int cap);
};
template <typename E>
void Array<E>::ensureCapacity(long long int cap) {
  capacity = capacity * 2;
  E* newArray = new E[capacity];
  memcpy(newArray, array, sizeof(E) * size);
  delete[] array;
  array = newArray;
}
template <typename E>
void Array<E>::fill() {
  for (long long int i = 0; i < size; i++) {
    array[i] = 0;
  }
}
template <>
void Array<pair<long long int, long long int> >::fill() {
  for (long long int i = 0; i < size; i++) {
    array[i] = make_pair(0, 0);
  }
}
template <>
void Array<string>::fill() {
  for (long long int i = 0; i < size; i++) {
    array[i] = "";
  }
}
template <typename E>
void Array<E>::toString(ostream& stream) {
  long long int i = 0;
  while (i < size) {
    if (i == size - 1) {
      stream << array[i];
    } else {
      stream << array[i] << " ";
    }
    i++;
  }
  stream << endl;
}
template <typename E>
void Array<E>::add(E item) {
  if (capacity < size + 1) {
    ensureCapacity(size + 1);
  }
  array[size] = item;
  size++;
}
template <typename E>
E* Array<E>::begin() {
  return array;
}
template <typename E>
E* Array<E>::end() {
  return array + size;
}
template <typename E>
long long int Array<E>::leftBinarySearch(E& item) {
  return lower_bound(array, array + size, item) - array;
}
template <typename E>
long long int Array<E>::rightBinarySearch(E& item) {
  return upper_bound(array, array + size, item) - array;
}
template <typename E>
pair<long long int, long long int> Array<E>::equalRange(E& item) {
  pair<long long int*, long long int*> p(0, 0);
  p = equal_range(array, array + size, item);
  return make_pair(p.first - array, p.second - array);
}
template <typename E>
bool Array<E>::binarySearch(E& item) {
  return binary_search(array, array + size, item);
}
template <typename E>
vector<E> Array<E>::toVector() {
  vector<E> res = vector<E>(size);
  for (long long int i = 0; i < res.size(); i++) {
    res[i] = array[i];
  }
  return res;
}
template <typename T>
ostream& operator<<(ostream& out, Array<T>& c) {
  c.toString(out);
  return out;
}
ostream& operator<<(ostream& out,
                    Array<pair<long long int, long long int> >& c) {
  for (long long int i = 0; i < c.size; i++) {
    out << c[i];
  }
  return out;
}
template <typename T>
istream& operator>>(istream& in, Array<T>& c) {
  for (long long int i = 0; i < c.size; i++) {
    c[i] = read<T>();
  }
  return in;
}
ostream& operator<<(ostream& out, map<long long int, long long int>& c) {
  map<long long int, long long int>::iterator it = c.begin();
  while (it != c.end()) {
    pair<long long int, long long int> entry = *it;
    out << entry;
    it++;
  }
  return out;
}
Array<pair<long long int, long long int> > mapToArray(
    map<long long int, long long int>& c) {
  Array<pair<long long int, long long int> > res(c.size());
  map<long long int, long long int>::iterator it = c.begin();
  long long int i = 0;
  while (it != c.end()) {
    pair<long long int, long long int> entry = *it;
    res[i] = entry;
    i++;
    it++;
  }
  return res;
}
template <typename E>
E& Array<E>::operator[](long long int i) {
  if (i < size && i >= 0) {
    return array[i];
  } else {
    cout << "Array index out of bounds, index is " << i << ", size is " << size
         << endl;
    cout << "Array is " << endl;
    toString(cout);
    assert(0);
  }
}
template <typename E>
class Matrix {
 public:
  long long int rows;
  long long int columns;
  Array<E> array;
  E& get(long long int x, long long int y);
  void set(long long int x, long long int y, E& value);
  E& operator()(long long int x, long long int y);
  Matrix<E> transpose();
  pair<E*, E*> getRow(long long int y);
  Matrix<E>(long long int c, long long int r) {
    rows = r;
    columns = c;
    array = Array<E>(rows * columns);
    array.fill();
  }
  void swap(Matrix<E>& other) {
    std::swap(array, other.array);
    std::swap(rows, other.rows);
    std::swap(columns, other.columns);
  }
  Matrix<E>(long long int _columns, long long int _rows, long long int minBound,
            long long int maxBound) {
    rows = _rows;
    columns = _columns;
    long long int size = _rows * _columns;
    array = Array<E>(minBound, maxBound, size);
  }

 private:
};
template <typename E>
Matrix<E> Matrix<E>::transpose() {
  Matrix<long long int> b(rows, columns);
  for (long long int x = 0; x < columns; x++) {
    for (long long int y = 0; y < rows; y++) {
      b(y, x) = array.array[x + y * columns];
    }
  }
  return b;
}
template <typename E>
E& Matrix<E>::operator()(long long int x, long long int y) {
  if (x >= columns || x < 0) {
    cout << "x must be in range [0; " << columns - 1 << "], but it is " << x
         << endl;
    assert(0);
  }
  if (y >= rows || y < 0) {
    cout << "y must be in range [0; " << rows - 1 << "], but it is " << y
         << endl;
    assert(0);
  }
  return array.array[x + y * columns];
}
template <typename T>
istream& operator>>(istream& in, Matrix<T>& c) {
  for (long long int y = 0; y < c.rows; y++) {
    for (long long int x = 0; x < c.columns; x++) {
      c(x, y) = read<T>();
    }
  }
  return in;
}
template <typename E>
pair<E*, E*> Matrix<E>::getRow(long long int y) {
  E* f = array.array + y * columns;
  E* s = array.array + (y + 1) * columns;
  pair<E*, E*> p(f, s);
  return p;
}
template <typename T>
ostream& operator<<(ostream& out, Matrix<T>& c) {
  for (size_t y = 0; y < c.rows; y++) {
    for (size_t x = 0; x < c.columns; x++) {
      out << c(x, y) << " ";
    }
    out << endl;
  }
}
class Point {
 public:
  double x;
  double y;
  Point(double _x, double _y) {
    x = _x;
    y = _y;
  }
  Point() {
    x = 0;
    y = 0;
  }
};
double dist(Point& a, Point& b) {
  double dx = a.x - b.x;
  double dy = a.y - b.y;
  return sqrt(dx * dx + dy * dy);
}
bool cmp(double a, double b) {
  if (fabs(a - b) < EPS) {
    return true;
  } else {
    return false;
  }
}
class Triangle {
 public:
  Point A;
  Point B;
  Point C;
  double a;
  double b;
  double c;
  Triangle(Point _A, Point _B, Point _C) {
    A = _A;
    B = _B;
    C = _C;
    a = dist(C, B);
    b = dist(C, A);
    c = dist(A, B);
  }
  Triangle() {}
  double S() {
    return fabs((B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y));
  }
};
class Line {
 public:
  double A;
  double B;
  double C;
  double xmin;
  double xmax;
  Line(Point _A, Point _B, bool isSegment) { set(_A, _B, isSegment); }
  void set(Point _A, Point _B, bool isSegment) {
    if (isSegment) {
      xmin = min(_A.x, _B.x);
      xmax = max(_A.x, _B.x);
    } else {
      xmin = -INF;
      xmax = INF;
    }
    double k = (_B.y - _A.y) / (_B.x - _A.x);
    double b = _A.y - k * _A.x;
    A = k;
    B = -1.0;
    C = b;
  }
  void setSegment(Point _A, Point _B) { set(_A, _B, true); }
  void setLine(Point _A, Point _B) { set(_A, _B, false); }
  double getY(double x) { return A * x + C; }
  double length() {
    double x1 = xmin;
    double y1 = getY(xmin);
    double x2 = xmax;
    double y2 = getY(xmax);
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
  }
  long long int part(Point p) {
    if (fabs(A) > 100000000.0) {
      if (cmp(p.x, xmin)) {
        return 0;
      }
      if (p.x > xmin) {
        return 1;
      } else {
        return -1;
      }
    }
    if (cmp(A * p.x + B * p.y + C, 0.0)) {
      return 0;
    }
    if (A * p.x + B * p.y + C > 0) {
      return 1;
    }
    if (A * p.x + B * p.y + C < 0) {
      return -1;
    }
  }
};
istream& operator>>(istream& in, Point& c) {
  c.x = read<long long int>();
  c.y = read<long long int>();
}
ostream& operator<<(ostream& out, Point& c) {
  out << "[" << c.x << ", " << c.y << "]" << endl;
}
istream& operator>>(istream& in, Triangle& c) {
  in >> c.A;
  in >> c.B;
  in >> c.C;
}
ostream& operator<<(ostream& out, Triangle& c) {
  out << c.A;
  out << c.B;
  out << c.C;
}
istream& operator>>(istream& in, Line& c) {
  Point a;
  Point b;
  in >> a;
  in >> b;
  c.setLine(a, b);
}
ostream& operator<<(ostream& out, Line& c) {
  cout << "y = " << c.A << "*x + " << c.C;
}
long long int bpow(long long int a, long long int b) {
  if (b == 0) {
    return 1;
  } else {
    if (b % 2 == 0) {
      long long int half = bpow(a, b / 2);
      return half * half;
    } else {
      return bpow(a, b - 1) * a;
    }
  }
}
long long int fact(long long int n) {
  if (n == 1) {
    return 1;
  } else {
    return n * fact(n - 1);
  }
}
long long int gcd(long long int a, long long int b) {
  if (!b) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}
Array<pair<long long int, long long int> > factorize(long long int n) {
  Array<pair<long long int, long long int> > res;
  for (long long int i = 2; i < sqrt((double)n) + 1; i++) {
    if (n % i == 0) {
      pair<long long int, long long int> comp = make_pair(i, 1);
      n /= i;
      while (n % i == 0) {
        comp.second++;
        n /= i;
      }
      res.add(comp);
    }
  }
  if (n > 1) {
    res.add(make_pair(n, 1));
  }
  return res;
}
long long int euler(long long int n) {
  Array<pair<long long int, long long int> > fact = factorize(n);
  long long int res = 1;
  for (unsigned long long int i = 0; i < fact.size; i++) {
    long long int factor =
        pow((double)fact[i].first, (double)fact[i].second) -
        pow((double)fact[i].first, (double)fact[i].second - 1);
    res *= factor;
  }
  return res;
}
long long int inversePrime(long long int a, long long int m) {
  return bpow(a, m - 2) % m;
}
long long int inverseCoprimes(long long int a, long long int m) {
  return bpow(a, euler(m) - 1) % m;
}
long long int inverse(long long int a, long long int m) {
  if (gcd(a, m) == 1) {
    return inverseCoprimes(a, m);
  } else {
    assert(0);
    return -1;
  }
}
Array<long long int> enumerateDivisors(long long int n) {
  Array<pair<long long int, long long int> > divs = factorize(n);
  vector<long long int> totals = vector<long long int>(divs.size + 1);
  totals[0] = 1;
  for (unsigned long long int i = 1; i < divs.size + 1; i++) {
    totals[i] = totals[i - 1] * (divs[i - 1].second + 1);
  }
  Array<long long int> res;
  for (long long int i = 0; i < totals[totals.size() - 1]; i++) {
    vector<long long int> values = vector<long long int>(divs.size);
    for (unsigned long long int j = 0; j < values.size(); j++) {
      values[j] = (i / totals[j]) % (divs[j].second + 1);
    }
    long long int r = 1;
    for (unsigned long long int i = 0; i < values.size(); i++) {
      r *= bpow(divs[i].first, values[i]);
    }
    res.add(r);
  }
  return res;
}
void reverse(char* str) {
  char temp;
  size_t len = strlen(str) - 1;
  size_t i;
  size_t k = len;
  for (i = 0; i < len; i++) {
    temp = str[k];
    str[k] = str[i];
    str[i] = temp;
    k--;
    if (k == (len / 2)) {
      break;
    }
  }
}
map<long long int, long long int> count(Array<long long int> a) {
  map<long long int, long long int> res;
  for (long long int i = 0; i < a.size; i++) {
    res[a[i]]++;
  }
  return res;
}
void itoa(long long int n, char s[]) {
  long long int radix = 10;
  long long int i, sign;
  if ((sign = n) < 0) n = -n;
  i = 0;
  do {
    s[i++] = n % radix + '0';
  } while ((n /= radix) > 0);
  if (sign < 0) s[i++] = '-';
  s[i] = '\0';
  reverse(s);
}
long long int* vectorToArray(vector<long long int> v) {
  long long int* a = new long long int[v.size()];
  for (unsigned long long int i = 0; i < v.size(); i++) {
    a[i] = v[i];
  }
  return a;
}
char* stringToNumber(long long int number) {
  char* res = new char[100];
  itoa(number, res);
  return res;
}
long long int numberToString(char* str) { return atoi(str); }
long long int booleanAnswerBinarySearch(Array<long long int> params,
                                        long long int left, long long int right,
                                        bool (*f)(Array<long long int> params,
                                                  long long int v)) {
  if (f(params, left) && !f(params, left - 1)) {
    return left;
  }
  if (f(params, right) && !f(params, right + 1)) {
    return right;
  }
  long long int middle = (left + right) / 2;
  long long int g = f(params, middle);
  if (g) {
    return booleanAnswerBinarySearch(params, left, middle, f);
  } else {
    return booleanAnswerBinarySearch(params, middle + 1, right, f);
  }
}
Array<Array<long long int> > enumerarePermutations(long long int n) {
  long long int fac = fact(n);
  Array<long long int> v;
  for (long long int i = 0; i < n; i++) {
    v.add(i + 1);
  }
  Array<Array<long long int> > res;
  for (long long int i = 0; i < fac - 1; i++) {
    Array<long long int> c(n);
    copy(v.array, v.array + v.size, c.array);
    res.add(c);
    next_permutation(v.array, v.array + v.size);
  }
  Array<long long int> c(n);
  copy(v.array, v.array + v.size, c.array);
  res.add(c);
  return res;
}
template <typename T>
Array<Array<T> > enumerarePermutations(Array<T> array) {
  long long int n = array.size;
  long long int fac = fact(n);
  Array<T> v;
  for (long long int i = 0; i < n; i++) {
    v.add(array[i]);
  }
  Array<Array<T> > res;
  for (long long int i = 0; i < fac - 1; i++) {
    Array<T> c(n);
    copy(v.array, v.array + v.size, c.array);
    res.add(c);
    next_permutation(v.array, v.array + v.size);
  }
  Array<T> c(n);
  copy(v.array, v.array + v.size, c.array);
  res.add(c);
  return res;
}
Array<Array<long long int> > enumerareTuples(long long int n, long long int k) {
  long long int q = bpow(k, n);
  Array<Array<long long int> > res(q);
  for (long long int i = 0; i < q; i++) {
    Array<long long int> tuple(n);
    for (long long int j = 0; j < n; j++) {
      tuple[j] = (i / bpow(k, j)) % k;
    }
    res[i] = tuple;
  }
  return res;
}
template <typename T>
Array<Array<long long int> > enumerareTuples(long long int n, Array<T> array) {
  long long int k = array.size;
  long long int q = bpow(k, n);
  Array<Array<T> > res(q);
  for (long long int i = 0; i < q; i++) {
    Array<long long int> tuple(n);
    for (long long int j = 0; j < n; j++) {
      tuple[j] = array[(i / bpow(k, j)) % k];
    }
    res[i] = tuple;
  }
  return res;
}
bool* sieve(long long int bound) {
  bool* array = new bool[bound + 1]();
  for (long long int i = 2; i * i <= bound; i++) {
    if (!array[i]) {
      for (long long int j = i + i; j <= bound; j += i) {
        array[j] = 1;
      }
    }
  }
  return array;
}
long long int f(long long int k) { return k & (k + 1); }
string alignLeft(string a, long long int length, char ch) {
  if (a.length() < length) {
    a = string(length - a.length(), ch) + a;
  }
  return a;
}
string decToRadix(long long int n, long long int radix) {
  string res("");
  if (n == 0) {
    res.push_back('0');
    return res;
  }
  while (n) {
    long long int digit = n % radix;
    res.push_back((char)(digit + '0'));
    n /= radix;
  }
  reverse(res.begin(), res.end());
  return res;
}
long long int radixToDec(string s, long long int radix) {
  long long int res = 0;
  reverse(s.begin(), s.end());
  for (long long int i = 0; i < s.length(); i++) {
    res += (s[i] - '0') * bpow(radix, i);
  }
  return res;
}
class F {
 public:
  long long int (*f)(long long int, long long int);
  long long int (*inverse)(long long int, long long int);
  long long int NEUTRAL;
  F(long long int (*pf)(long long int, long long int),
    long long int (*pinverse)(long long int, long long int), long long int n) {
    f = pf;
    inverse = pinverse;
    NEUTRAL = n;
  }
  F() {}
  long long int operator()(long long int a, long long int b) { return f(a, b); }
  long long int inversed(long long int a, long long int b) {
    return inverse(a, b);
  }
};
class BIT {
 public:
  F f;
  Array<long long int> tree;
  Array<long long int> array;
  BIT(F func, Array<long long int> source) {
    Array<long long int> arr(source.size);
    copy(source.begin(), source.end(), arr.begin());
    array = arr;
    f = func;
    Array<long long int> tr(source.size);
    tree = tr;
    for (long long int i = 0; i < source.size; i++) {
      add(i, array[i]);
    }
  }
  void add(long long int i, long long int delta) {
    for (long long int u = i; u < tree.size; u = u | (u + 1)) {
      tree[u] = f(tree[u], delta);
    }
  }
  long long int value(long long int l, long long int r) {
    return f.inversed(p(r), p(l - 1));
  }
  long long int p(long long int v) {
    if (v < 0) {
      return 0;
    }
    if (v == 0) {
      return tree[0];
    } else {
      return f(tree[v], p((v & (v + 1)) - 1));
    }
  }
};
class Graph {
 public:
  long long int n = 0;
  long long int m = 0;
  vector<vector<long long int> > adj;
  vector<vector<long long int> > w;
  bool isDirected = false;
  bool isWeighted = false;
  Graph() {}
  void setDirected() { this->isDirected = true; }
  void setWeighted() { this->isWeighted = true; }
  Graph(long long int n) {
    this->n = n;
    vector<vector<long long int> > _adj(2 * n + 1);
    vector<vector<long long int> > _w(2 * n + 1);
    adj = _adj;
    w = _w;
  }
  void readByMatrix() {
    bool last = this->isDirected;
    this->isDirected = true;
    for (long long int i = 0; i < n; i++) {
      for (long long int j = 0; j < n; j++) {
        long long int x;
        cin >> x;
        if (this->isWeighted) {
          if (x != -1) {
            this->addWeighted(i, j, x);
          }
        } else {
          if (x != 0) {
            this->add(i, j);
          }
        }
      }
    }
    this->isDirected = last;
  }
  void printWeights() {
    for (long long int i = 0; i < n; i++) {
      cout << i << " {";
      for (long long int j = 0; j < w[i].size(); j++) {
        if (j != adj[i].size() - 1) {
          cout << w[i][j] << " ";
        } else {
          cout << w[i][j];
        }
      }
      cout << "}";
      cout << endl;
    }
  }
  void add(long long int a, long long int b) {
    this->m++;
    adj[a].push_back(b);
    if (!this->isDirected) {
      this->m++;
      adj[b].push_back(a);
    }
  }
  void addWeighted(long long int a, long long int b, long long int weight) {
    this->m++;
    adj[a].push_back(b);
    w[a].push_back(weight);
    if (!this->isDirected) {
      this->m++;
      adj[b].push_back(a);
      w[b].push_back(weight);
    }
  }
  void dfs(long long int v, long long int* p, vector<long long int>& graypath,
           Array<long long int>& cycles, Array<long long int>& res,
           Array<long long int>& outs, long long int* color) {
    color[v] = 1;
    res.add(v);
    graypath.push_back(v);
    for (long long int i = 0; i < adj[v].size(); i++) {
      long long int u = adj[v][i];
      if (color[u] == 0) {
        p[u] = v;
        dfs(u, p, graypath, cycles, res, outs, color);
      }
      if (color[u] == 1) {
        if (p[v] != u) {
          Array<long long int> cycle;
          bool now = false;
          for (long long int i = 0; i < graypath.size(); i++) {
            if (graypath[i] == u) {
              now = true;
            }
            if (now) {
              cycle.add(graypath[i]);
            }
            if (graypath[i] == v) {
              now = false;
            }
          }
          cycles = cycle;
        }
      }
    }
    graypath.pop_back();
    color[v] = 2;
    outs.add(v);
  }
  Array<long long int> dfs(long long int number) {
    long long int* color = new long long int[n]();
    long long int* p = new long long int[n]();
    Array<long long int> res;
    Array<long long int> outs;
    Array<long long int> cycles;
    vector<long long int> path;
    dfs(number, p, path, cycles, res, outs, color);
    return res;
  }
  Array<Array<long long int> > findConnectedComponents() {
    Array<Array<long long int> > res;
    long long int* array = new long long int[n]();
    for (long long int i = 0; i < n; i++) {
      if (!array[i]) {
        Array<long long int> component = dfs(i);
        for (long long int j = 0; j < component.size; j++) {
          array[component[j]] = i + 1;
        }
        res.add(component);
      }
    }
    return res;
  }
  void shortestPath(Array<long long int>& p, long long int from,
                    long long int to, Array<long long int>& res) {
    if (from == to) {
      res.add(from);
    } else {
      res.add(to);
      long long int newTo = p[to];
      shortestPath(p, from, newTo, res);
    }
  }
  Array<long long int> shortestPath(Array<long long int>& p, long long int from,
                                    long long int to) {
    Array<long long int> res;
    shortestPath(p, from, to, res);
    reverse(res.begin(), res.end());
    return res;
  }
  Array<long long int> bfsPath(long long int s, long long int t) {
    Array<long long int> p(n);
    Array<long long int> dists(n);
    bfs(p, dists, s);
    for (long long int i = 0; i < n; i++) {
      dists[i] = -1;
    }
    return shortestPath(p, s, t);
  }
  Array<long long int> bfsDists(long long int root) {
    Array<long long int> p(n);
    Array<long long int> dists(n);
    for (long long int i = 0; i < n; i++) {
      dists[i] = -1;
    }
    bfs(p, dists, root);
    return dists;
  }
  Array<long long int> findCycles() {
    long long int* color = new long long int[n]();
    long long int* p = new long long int[n]();
    Array<long long int> res;
    Array<long long int> outs;
    Array<long long int> cycles;
    vector<long long int> graypath;
    dfs(0, p, graypath, cycles, res, outs, color);
    return cycles;
  }
  void bfs(Array<long long int>& p, Array<long long int>& dists,
           long long int root) {
    queue<long long int> q;
    q.push(root);
    long long int* visited = new long long int[this->n]();
    visited[root] = true;
    dists[root] = 0;
    while (!q.empty()) {
      long long int v = q.front();
      q.pop();
      for (long long int i = 0; i < adj[v].size(); i++) {
        long long int u = adj[v][i];
        if (!visited[u]) {
          visited[u] = true;
          dists[u] = dists[v] + 1;
          p[u] = v;
          q.push(u);
        }
      }
    }
  }
  Array<long long int> toposort() {
    n++;
    vector<long long int> newAdj;
    adj[n] = newAdj;
    for (long long int i = 0; i < n - 1; i++) {
      this->add(n - 1, i);
    }
    Array<long long int> res;
    Array<long long int> outs;
    vector<long long int> path;
    Array<long long int> cycles;
    long long int* color = new long long int[n]();
    long long int* pr = new long long int[n]();
    dfs(n - 1, pr, path, cycles, res, outs, color);
    n--;
    Array<long long int> p(outs.size - 1);
    for (long long int i = 0; i < outs.size - 1; i++) {
      p[i] = outs[i];
    }
    reverse(p.begin(), p.end());
    Array<long long int> r(p.size);
    for (long long int i = 0; i < p.size; i++) {
      r[p[i]] = i;
    }
    for (long long int i = 0; i < n; i++) {
      for (long long int j = 0; j < adj[i].size(); j++) {
        long long int v = adj[i][j];
        if (r[i] >= r[v]) {
          Array<long long int> sh(0);
          return sh;
        }
      }
    }
    return p;
  }
  long long int INF = 1000000000;
  long long int INFP = 1000000000 / 2;
  void Dijkstra(Array<long long int>& p, Array<long long int>& d,
                long long int s) {
    for (long long int i = 0; i < n; i++) {
      d.add(this->INF);
    }
    d[s] = 0;
    for (long long int i = 0; i < n; i++) {
      p.add(this->INF);
    }
    p[s] = s;
    set<pair<long long int, long long int> > q;
    q.insert(make_pair(d[s], s));
    while (!q.empty()) {
      long long int v = q.begin()->second;
      q.erase(q.begin());
      for (size_t j = 0; j < adj[v].size(); ++j) {
        long long int to = adj[v][j];
        long long int len = w[v][j];
        if (d[v] + len < d[to]) {
          q.erase(make_pair(d[to], to));
          d[to] = d[v] + len;
          p[to] = v;
          q.insert(make_pair(d[to], to));
        }
      }
    }
  }
};
long long int clp2(long long int x) {
  x--;
  for (long long int p = 1; p < 32; p <<= 1) x |= (x >> p);
  return ++x;
}
void fillArray(Array<long long int>& a) {
  long long int need = clp2(a.size);
  for (long long int i = a.size; i < need; i++) {
    a.add(0);
  }
}
istream& operator>>(istream& in, Graph& g) {
  long long int n;
  long long int m;
  cin >> n >> m;
  Graph graph(n);
  graph.isDirected = g.isDirected;
  graph.isWeighted = g.isWeighted;
  for (long long int i = 0; i < m; i++) {
    long long int x;
    long long int y;
    cin >> x >> y;
    if (!graph.isWeighted) {
      graph.add(x - 1, y - 1);
    } else {
      long long int w;
      cin >> w;
      graph.addWeighted(x - 1, y - 1, w);
    }
  }
  g = graph;
  return in;
}
ostream& operator<<(ostream& out, Graph& g) {
  for (long long int i = 0; i < g.n; i++) {
    out << i << " {";
    for (long long int j = 0; j < g.adj[i].size(); j++) {
      if (j != g.adj[i].size() - 1) {
        out << g.adj[i][j] << " ";
      } else {
        out << g.adj[i][j];
      }
    }
    out << "}";
    out << endl;
  }
  return out;
}
int main(void) {
  RANDOM = 0;
  srand(time(0));
  long long int a;
  long long int b;
  cin >> a >> b;
  long long int maxCom = min(a, b);
  long long int maxRes = 0;
  for (long long int f = 0; f <= maxCom; f++) {
    long long int o1 = f;
    long long int n1 = 2 * f;
    long long int orest = a - o1;
    long long int nrest = b - n1;
    if (orest >= 0 && nrest >= 0) {
      long long int s = min(orest / 2, nrest);
      long long int total = s + f;
      if (total > maxRes) {
        maxRes = total;
      }
    }
  }
  cout << maxRes;
}

### Prompt

Construct a CPP code solution to the problem outlined:

A and B are preparing themselves for programming contests.

An important part of preparing for a competition is sharing programming knowledge from the experienced members to those who are just beginning to deal with the contests. Therefore, during the next team training A decided to make teams so that newbies are solving problems together with experienced participants.

A believes that the optimal team of three people should consist of one experienced participant and two newbies. Thus, each experienced participant can share the experience with a large number of people.

However, B believes that the optimal team should have two experienced members plus one newbie. Thus, each newbie can gain more knowledge and experience.

As a result, A and B have decided that all the teams during the training session should belong to one of the two types described above. Furthermore, they agree that the total number of teams should be as much as possible.

There are n experienced members and m newbies on the training session. Can you calculate what maximum number of teams can be formed?

Input

The first line contains two integers n and m (0 ≤ n, m ≤ 5·105) — the number of experienced participants and newbies that are present at the training session. 

Output

Print the maximum number of teams that can be formed.

Examples

Input

2 6


Output

2


Input

4 5


Output

3

Note

Let's represent the experienced players as XP and newbies as NB.

In the first test the teams look as follows: (XP, NB, NB), (XP, NB, NB).

In the second test sample the teams look as follows: (XP, NB, NB), (XP, NB, NB), (XP, XP, NB).

### Response

```cpp
#include <bits/stdc++.h>
bool RANDOM = false;
using namespace std;
double EPS = 0.0000000001;
double INF = 1000000000000000.0;
ostream_iterator<long long int> oi(cout, " ");
long long int minInt = 1;
long long int maxInt = 100;
double minDouble = -100000000000.0;
double maxDouble = 100000000000.0;
void setMaxInt(long long int newMax) { maxInt = newMax; }
void setMinInt(long long int newMin) { minInt = newMin; }
void setIntRange(long long int min, long long int max) {
  maxInt = max;
  minInt = min;
}
void setMaxDouble(double newMax) { maxDouble = newMax; }
void setMinDouble(double newMin) { minDouble = newMin; }
void setDoubleRange(double min, double max) {
  maxDouble = max;
  minDouble = min;
}
ostream& operator<<(ostream& out, pair<long long int, long long int>& c) {
  out << "<" << c.first << ", ";
  out << c.second << ">" << endl;
  return out;
}
void print() { std::cout << endl; }
template <typename A>
void print(A value) {
  std::cout << value;
}
template <typename A, typename B>
void print(A value1, B value2) {
  cout << value1 << " " << value2;
}
template <typename A, typename B, typename C>
void print(A value1, B value2, C value3) {
  cout << value1 << " " << value2 << " " << value3;
}
template <typename A, typename B, typename C, typename D>
void print(A value1, B value2, C value3, D value4) {
  cout << value1 << " " << value2 << " " << value3 << " " << value4;
}
template <typename A>
void println(A value) {
  std::cout << value << endl;
}
template <typename A, typename B>
void println(A value1, B value2) {
  cout << value1 << " " << value2 << endl;
}
template <typename A, typename B, typename C>
void println(A value1, B value2, C value3) {
  cout << value1 << " " << value2 << " " << value3 << endl;
}
template <typename A, typename B, typename C, typename D>
void println(A value1, B value2, C value3, D value4) {
  cout << value1 << " " << value2 << " " << value3 << " " << value4 << endl;
}
long long int randomint(long long int min, long long int max) {
  return rand() % (max - min + 1) + min;
}
double randomdouble(double min, double max) {
  return (rand() / (double)RAND_MAX) * (max - min) + min;
}
template <typename E>
E read() {
  E value;
  cin >> value;
  return value;
}
template <>
long long int read<long long int>() {
  if (!RANDOM) {
    long long int value;
    cin >> value;
    return value;
  } else {
    return randomint(minInt, maxInt);
  }
}
template <>
double read<double>() {
  if (!RANDOM) {
    double value;
    cin >> value;
    return value;
  } else {
    return randomdouble(minDouble, maxDouble);
  }
}
istream& operator>>(istream& in, pair<long long int, long long int>& c) {
  c.first = read<long long int>();
  c.second = read<long long int>();
  return in;
}
ostream& operator<<(ostream& out, string& c) {
  for (long long int i = 0; i < c.length(); i++) {
    putchar(c[i]);
  }
  return out;
}
template <typename E>
class Array {
 public:
  long long int size;
  Array<E>(long long int _capacity) {
    capacity = _capacity;
    array = new E[capacity];
    size = capacity;
    fill();
  }
  void sort() { std::sort(&array[0], &array[size]); }
  Array() {
    capacity = 4;
    array = new E[capacity];
    size = 0;
  }
  Array(vector<E>& vect) {
    long long int _size = vect.size();
    capacity = _size * 2;
    size = _size;
    array = new E[capacity];
    for (long long int i = 0; i < size; i++) {
      array[i] = vect[i];
    }
  }
  Array(long long int minBound, long long int maxBound, long long int _size) {
    srand(_size);
    capacity = _size * 2;
    size = _size;
    array = new E[capacity];
    for (long long int i = 0; i < size; i++) {
      array[i] = randomint(minBound, maxBound);
    }
  }
  void add(E item);
  long long int leftBinarySearch(E& item);
  long long int rightBinarySearch(E& item);
  pair<long long int, long long int> equalRange(E& item);
  bool binarySearch(E& item);
  void fill();
  E* begin();
  E* end();
  vector<E> toVector();
  void toString(ostream& stream);
  E& operator[](long long int i);
  E& index(long long int i);
  E* array;

 private:
  long long int capacity;
  void ensureCapacity(long long int cap);
};
template <typename E>
void Array<E>::ensureCapacity(long long int cap) {
  capacity = capacity * 2;
  E* newArray = new E[capacity];
  memcpy(newArray, array, sizeof(E) * size);
  delete[] array;
  array = newArray;
}
template <typename E>
void Array<E>::fill() {
  for (long long int i = 0; i < size; i++) {
    array[i] = 0;
  }
}
template <>
void Array<pair<long long int, long long int> >::fill() {
  for (long long int i = 0; i < size; i++) {
    array[i] = make_pair(0, 0);
  }
}
template <>
void Array<string>::fill() {
  for (long long int i = 0; i < size; i++) {
    array[i] = "";
  }
}
template <typename E>
void Array<E>::toString(ostream& stream) {
  long long int i = 0;
  while (i < size) {
    if (i == size - 1) {
      stream << array[i];
    } else {
      stream << array[i] << " ";
    }
    i++;
  }
  stream << endl;
}
template <typename E>
void Array<E>::add(E item) {
  if (capacity < size + 1) {
    ensureCapacity(size + 1);
  }
  array[size] = item;
  size++;
}
template <typename E>
E* Array<E>::begin() {
  return array;
}
template <typename E>
E* Array<E>::end() {
  return array + size;
}
template <typename E>
long long int Array<E>::leftBinarySearch(E& item) {
  return lower_bound(array, array + size, item) - array;
}
template <typename E>
long long int Array<E>::rightBinarySearch(E& item) {
  return upper_bound(array, array + size, item) - array;
}
template <typename E>
pair<long long int, long long int> Array<E>::equalRange(E& item) {
  pair<long long int*, long long int*> p(0, 0);
  p = equal_range(array, array + size, item);
  return make_pair(p.first - array, p.second - array);
}
template <typename E>
bool Array<E>::binarySearch(E& item) {
  return binary_search(array, array + size, item);
}
template <typename E>
vector<E> Array<E>::toVector() {
  vector<E> res = vector<E>(size);
  for (long long int i = 0; i < res.size(); i++) {
    res[i] = array[i];
  }
  return res;
}
template <typename T>
ostream& operator<<(ostream& out, Array<T>& c) {
  c.toString(out);
  return out;
}
ostream& operator<<(ostream& out,
                    Array<pair<long long int, long long int> >& c) {
  for (long long int i = 0; i < c.size; i++) {
    out << c[i];
  }
  return out;
}
template <typename T>
istream& operator>>(istream& in, Array<T>& c) {
  for (long long int i = 0; i < c.size; i++) {
    c[i] = read<T>();
  }
  return in;
}
ostream& operator<<(ostream& out, map<long long int, long long int>& c) {
  map<long long int, long long int>::iterator it = c.begin();
  while (it != c.end()) {
    pair<long long int, long long int> entry = *it;
    out << entry;
    it++;
  }
  return out;
}
Array<pair<long long int, long long int> > mapToArray(
    map<long long int, long long int>& c) {
  Array<pair<long long int, long long int> > res(c.size());
  map<long long int, long long int>::iterator it = c.begin();
  long long int i = 0;
  while (it != c.end()) {
    pair<long long int, long long int> entry = *it;
    res[i] = entry;
    i++;
    it++;
  }
  return res;
}
template <typename E>
E& Array<E>::operator[](long long int i) {
  if (i < size && i >= 0) {
    return array[i];
  } else {
    cout << "Array index out of bounds, index is " << i << ", size is " << size
         << endl;
    cout << "Array is " << endl;
    toString(cout);
    assert(0);
  }
}
template <typename E>
class Matrix {
 public:
  long long int rows;
  long long int columns;
  Array<E> array;
  E& get(long long int x, long long int y);
  void set(long long int x, long long int y, E& value);
  E& operator()(long long int x, long long int y);
  Matrix<E> transpose();
  pair<E*, E*> getRow(long long int y);
  Matrix<E>(long long int c, long long int r) {
    rows = r;
    columns = c;
    array = Array<E>(rows * columns);
    array.fill();
  }
  void swap(Matrix<E>& other) {
    std::swap(array, other.array);
    std::swap(rows, other.rows);
    std::swap(columns, other.columns);
  }
  Matrix<E>(long long int _columns, long long int _rows, long long int minBound,
            long long int maxBound) {
    rows = _rows;
    columns = _columns;
    long long int size = _rows * _columns;
    array = Array<E>(minBound, maxBound, size);
  }

 private:
};
template <typename E>
Matrix<E> Matrix<E>::transpose() {
  Matrix<long long int> b(rows, columns);
  for (long long int x = 0; x < columns; x++) {
    for (long long int y = 0; y < rows; y++) {
      b(y, x) = array.array[x + y * columns];
    }
  }
  return b;
}
template <typename E>
E& Matrix<E>::operator()(long long int x, long long int y) {
  if (x >= columns || x < 0) {
    cout << "x must be in range [0; " << columns - 1 << "], but it is " << x
         << endl;
    assert(0);
  }
  if (y >= rows || y < 0) {
    cout << "y must be in range [0; " << rows - 1 << "], but it is " << y
         << endl;
    assert(0);
  }
  return array.array[x + y * columns];
}
template <typename T>
istream& operator>>(istream& in, Matrix<T>& c) {
  for (long long int y = 0; y < c.rows; y++) {
    for (long long int x = 0; x < c.columns; x++) {
      c(x, y) = read<T>();
    }
  }
  return in;
}
template <typename E>
pair<E*, E*> Matrix<E>::getRow(long long int y) {
  E* f = array.array + y * columns;
  E* s = array.array + (y + 1) * columns;
  pair<E*, E*> p(f, s);
  return p;
}
template <typename T>
ostream& operator<<(ostream& out, Matrix<T>& c) {
  for (size_t y = 0; y < c.rows; y++) {
    for (size_t x = 0; x < c.columns; x++) {
      out << c(x, y) << " ";
    }
    out << endl;
  }
}
class Point {
 public:
  double x;
  double y;
  Point(double _x, double _y) {
    x = _x;
    y = _y;
  }
  Point() {
    x = 0;
    y = 0;
  }
};
double dist(Point& a, Point& b) {
  double dx = a.x - b.x;
  double dy = a.y - b.y;
  return sqrt(dx * dx + dy * dy);
}
bool cmp(double a, double b) {
  if (fabs(a - b) < EPS) {
    return true;
  } else {
    return false;
  }
}
class Triangle {
 public:
  Point A;
  Point B;
  Point C;
  double a;
  double b;
  double c;
  Triangle(Point _A, Point _B, Point _C) {
    A = _A;
    B = _B;
    C = _C;
    a = dist(C, B);
    b = dist(C, A);
    c = dist(A, B);
  }
  Triangle() {}
  double S() {
    return fabs((B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y));
  }
};
class Line {
 public:
  double A;
  double B;
  double C;
  double xmin;
  double xmax;
  Line(Point _A, Point _B, bool isSegment) { set(_A, _B, isSegment); }
  void set(Point _A, Point _B, bool isSegment) {
    if (isSegment) {
      xmin = min(_A.x, _B.x);
      xmax = max(_A.x, _B.x);
    } else {
      xmin = -INF;
      xmax = INF;
    }
    double k = (_B.y - _A.y) / (_B.x - _A.x);
    double b = _A.y - k * _A.x;
    A = k;
    B = -1.0;
    C = b;
  }
  void setSegment(Point _A, Point _B) { set(_A, _B, true); }
  void setLine(Point _A, Point _B) { set(_A, _B, false); }
  double getY(double x) { return A * x + C; }
  double length() {
    double x1 = xmin;
    double y1 = getY(xmin);
    double x2 = xmax;
    double y2 = getY(xmax);
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
  }
  long long int part(Point p) {
    if (fabs(A) > 100000000.0) {
      if (cmp(p.x, xmin)) {
        return 0;
      }
      if (p.x > xmin) {
        return 1;
      } else {
        return -1;
      }
    }
    if (cmp(A * p.x + B * p.y + C, 0.0)) {
      return 0;
    }
    if (A * p.x + B * p.y + C > 0) {
      return 1;
    }
    if (A * p.x + B * p.y + C < 0) {
      return -1;
    }
  }
};
istream& operator>>(istream& in, Point& c) {
  c.x = read<long long int>();
  c.y = read<long long int>();
}
ostream& operator<<(ostream& out, Point& c) {
  out << "[" << c.x << ", " << c.y << "]" << endl;
}
istream& operator>>(istream& in, Triangle& c) {
  in >> c.A;
  in >> c.B;
  in >> c.C;
}
ostream& operator<<(ostream& out, Triangle& c) {
  out << c.A;
  out << c.B;
  out << c.C;
}
istream& operator>>(istream& in, Line& c) {
  Point a;
  Point b;
  in >> a;
  in >> b;
  c.setLine(a, b);
}
ostream& operator<<(ostream& out, Line& c) {
  cout << "y = " << c.A << "*x + " << c.C;
}
long long int bpow(long long int a, long long int b) {
  if (b == 0) {
    return 1;
  } else {
    if (b % 2 == 0) {
      long long int half = bpow(a, b / 2);
      return half * half;
    } else {
      return bpow(a, b - 1) * a;
    }
  }
}
long long int fact(long long int n) {
  if (n == 1) {
    return 1;
  } else {
    return n * fact(n - 1);
  }
}
long long int gcd(long long int a, long long int b) {
  if (!b) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}
Array<pair<long long int, long long int> > factorize(long long int n) {
  Array<pair<long long int, long long int> > res;
  for (long long int i = 2; i < sqrt((double)n) + 1; i++) {
    if (n % i == 0) {
      pair<long long int, long long int> comp = make_pair(i, 1);
      n /= i;
      while (n % i == 0) {
        comp.second++;
        n /= i;
      }
      res.add(comp);
    }
  }
  if (n > 1) {
    res.add(make_pair(n, 1));
  }
  return res;
}
long long int euler(long long int n) {
  Array<pair<long long int, long long int> > fact = factorize(n);
  long long int res = 1;
  for (unsigned long long int i = 0; i < fact.size; i++) {
    long long int factor =
        pow((double)fact[i].first, (double)fact[i].second) -
        pow((double)fact[i].first, (double)fact[i].second - 1);
    res *= factor;
  }
  return res;
}
long long int inversePrime(long long int a, long long int m) {
  return bpow(a, m - 2) % m;
}
long long int inverseCoprimes(long long int a, long long int m) {
  return bpow(a, euler(m) - 1) % m;
}
long long int inverse(long long int a, long long int m) {
  if (gcd(a, m) == 1) {
    return inverseCoprimes(a, m);
  } else {
    assert(0);
    return -1;
  }
}
Array<long long int> enumerateDivisors(long long int n) {
  Array<pair<long long int, long long int> > divs = factorize(n);
  vector<long long int> totals = vector<long long int>(divs.size + 1);
  totals[0] = 1;
  for (unsigned long long int i = 1; i < divs.size + 1; i++) {
    totals[i] = totals[i - 1] * (divs[i - 1].second + 1);
  }
  Array<long long int> res;
  for (long long int i = 0; i < totals[totals.size() - 1]; i++) {
    vector<long long int> values = vector<long long int>(divs.size);
    for (unsigned long long int j = 0; j < values.size(); j++) {
      values[j] = (i / totals[j]) % (divs[j].second + 1);
    }
    long long int r = 1;
    for (unsigned long long int i = 0; i < values.size(); i++) {
      r *= bpow(divs[i].first, values[i]);
    }
    res.add(r);
  }
  return res;
}
void reverse(char* str) {
  char temp;
  size_t len = strlen(str) - 1;
  size_t i;
  size_t k = len;
  for (i = 0; i < len; i++) {
    temp = str[k];
    str[k] = str[i];
    str[i] = temp;
    k--;
    if (k == (len / 2)) {
      break;
    }
  }
}
map<long long int, long long int> count(Array<long long int> a) {
  map<long long int, long long int> res;
  for (long long int i = 0; i < a.size; i++) {
    res[a[i]]++;
  }
  return res;
}
void itoa(long long int n, char s[]) {
  long long int radix = 10;
  long long int i, sign;
  if ((sign = n) < 0) n = -n;
  i = 0;
  do {
    s[i++] = n % radix + '0';
  } while ((n /= radix) > 0);
  if (sign < 0) s[i++] = '-';
  s[i] = '\0';
  reverse(s);
}
long long int* vectorToArray(vector<long long int> v) {
  long long int* a = new long long int[v.size()];
  for (unsigned long long int i = 0; i < v.size(); i++) {
    a[i] = v[i];
  }
  return a;
}
char* stringToNumber(long long int number) {
  char* res = new char[100];
  itoa(number, res);
  return res;
}
long long int numberToString(char* str) { return atoi(str); }
long long int booleanAnswerBinarySearch(Array<long long int> params,
                                        long long int left, long long int right,
                                        bool (*f)(Array<long long int> params,
                                                  long long int v)) {
  if (f(params, left) && !f(params, left - 1)) {
    return left;
  }
  if (f(params, right) && !f(params, right + 1)) {
    return right;
  }
  long long int middle = (left + right) / 2;
  long long int g = f(params, middle);
  if (g) {
    return booleanAnswerBinarySearch(params, left, middle, f);
  } else {
    return booleanAnswerBinarySearch(params, middle + 1, right, f);
  }
}
Array<Array<long long int> > enumerarePermutations(long long int n) {
  long long int fac = fact(n);
  Array<long long int> v;
  for (long long int i = 0; i < n; i++) {
    v.add(i + 1);
  }
  Array<Array<long long int> > res;
  for (long long int i = 0; i < fac - 1; i++) {
    Array<long long int> c(n);
    copy(v.array, v.array + v.size, c.array);
    res.add(c);
    next_permutation(v.array, v.array + v.size);
  }
  Array<long long int> c(n);
  copy(v.array, v.array + v.size, c.array);
  res.add(c);
  return res;
}
template <typename T>
Array<Array<T> > enumerarePermutations(Array<T> array) {
  long long int n = array.size;
  long long int fac = fact(n);
  Array<T> v;
  for (long long int i = 0; i < n; i++) {
    v.add(array[i]);
  }
  Array<Array<T> > res;
  for (long long int i = 0; i < fac - 1; i++) {
    Array<T> c(n);
    copy(v.array, v.array + v.size, c.array);
    res.add(c);
    next_permutation(v.array, v.array + v.size);
  }
  Array<T> c(n);
  copy(v.array, v.array + v.size, c.array);
  res.add(c);
  return res;
}
Array<Array<long long int> > enumerareTuples(long long int n, long long int k) {
  long long int q = bpow(k, n);
  Array<Array<long long int> > res(q);
  for (long long int i = 0; i < q; i++) {
    Array<long long int> tuple(n);
    for (long long int j = 0; j < n; j++) {
      tuple[j] = (i / bpow(k, j)) % k;
    }
    res[i] = tuple;
  }
  return res;
}
template <typename T>
Array<Array<long long int> > enumerareTuples(long long int n, Array<T> array) {
  long long int k = array.size;
  long long int q = bpow(k, n);
  Array<Array<T> > res(q);
  for (long long int i = 0; i < q; i++) {
    Array<long long int> tuple(n);
    for (long long int j = 0; j < n; j++) {
      tuple[j] = array[(i / bpow(k, j)) % k];
    }
    res[i] = tuple;
  }
  return res;
}
bool* sieve(long long int bound) {
  bool* array = new bool[bound + 1]();
  for (long long int i = 2; i * i <= bound; i++) {
    if (!array[i]) {
      for (long long int j = i + i; j <= bound; j += i) {
        array[j] = 1;
      }
    }
  }
  return array;
}
long long int f(long long int k) { return k & (k + 1); }
string alignLeft(string a, long long int length, char ch) {
  if (a.length() < length) {
    a = string(length - a.length(), ch) + a;
  }
  return a;
}
string decToRadix(long long int n, long long int radix) {
  string res("");
  if (n == 0) {
    res.push_back('0');
    return res;
  }
  while (n) {
    long long int digit = n % radix;
    res.push_back((char)(digit + '0'));
    n /= radix;
  }
  reverse(res.begin(), res.end());
  return res;
}
long long int radixToDec(string s, long long int radix) {
  long long int res = 0;
  reverse(s.begin(), s.end());
  for (long long int i = 0; i < s.length(); i++) {
    res += (s[i] - '0') * bpow(radix, i);
  }
  return res;
}
class F {
 public:
  long long int (*f)(long long int, long long int);
  long long int (*inverse)(long long int, long long int);
  long long int NEUTRAL;
  F(long long int (*pf)(long long int, long long int),
    long long int (*pinverse)(long long int, long long int), long long int n) {
    f = pf;
    inverse = pinverse;
    NEUTRAL = n;
  }
  F() {}
  long long int operator()(long long int a, long long int b) { return f(a, b); }
  long long int inversed(long long int a, long long int b) {
    return inverse(a, b);
  }
};
class BIT {
 public:
  F f;
  Array<long long int> tree;
  Array<long long int> array;
  BIT(F func, Array<long long int> source) {
    Array<long long int> arr(source.size);
    copy(source.begin(), source.end(), arr.begin());
    array = arr;
    f = func;
    Array<long long int> tr(source.size);
    tree = tr;
    for (long long int i = 0; i < source.size; i++) {
      add(i, array[i]);
    }
  }
  void add(long long int i, long long int delta) {
    for (long long int u = i; u < tree.size; u = u | (u + 1)) {
      tree[u] = f(tree[u], delta);
    }
  }
  long long int value(long long int l, long long int r) {
    return f.inversed(p(r), p(l - 1));
  }
  long long int p(long long int v) {
    if (v < 0) {
      return 0;
    }
    if (v == 0) {
      return tree[0];
    } else {
      return f(tree[v], p((v & (v + 1)) - 1));
    }
  }
};
class Graph {
 public:
  long long int n = 0;
  long long int m = 0;
  vector<vector<long long int> > adj;
  vector<vector<long long int> > w;
  bool isDirected = false;
  bool isWeighted = false;
  Graph() {}
  void setDirected() { this->isDirected = true; }
  void setWeighted() { this->isWeighted = true; }
  Graph(long long int n) {
    this->n = n;
    vector<vector<long long int> > _adj(2 * n + 1);
    vector<vector<long long int> > _w(2 * n + 1);
    adj = _adj;
    w = _w;
  }
  void readByMatrix() {
    bool last = this->isDirected;
    this->isDirected = true;
    for (long long int i = 0; i < n; i++) {
      for (long long int j = 0; j < n; j++) {
        long long int x;
        cin >> x;
        if (this->isWeighted) {
          if (x != -1) {
            this->addWeighted(i, j, x);
          }
        } else {
          if (x != 0) {
            this->add(i, j);
          }
        }
      }
    }
    this->isDirected = last;
  }
  void printWeights() {
    for (long long int i = 0; i < n; i++) {
      cout << i << " {";
      for (long long int j = 0; j < w[i].size(); j++) {
        if (j != adj[i].size() - 1) {
          cout << w[i][j] << " ";
        } else {
          cout << w[i][j];
        }
      }
      cout << "}";
      cout << endl;
    }
  }
  void add(long long int a, long long int b) {
    this->m++;
    adj[a].push_back(b);
    if (!this->isDirected) {
      this->m++;
      adj[b].push_back(a);
    }
  }
  void addWeighted(long long int a, long long int b, long long int weight) {
    this->m++;
    adj[a].push_back(b);
    w[a].push_back(weight);
    if (!this->isDirected) {
      this->m++;
      adj[b].push_back(a);
      w[b].push_back(weight);
    }
  }
  void dfs(long long int v, long long int* p, vector<long long int>& graypath,
           Array<long long int>& cycles, Array<long long int>& res,
           Array<long long int>& outs, long long int* color) {
    color[v] = 1;
    res.add(v);
    graypath.push_back(v);
    for (long long int i = 0; i < adj[v].size(); i++) {
      long long int u = adj[v][i];
      if (color[u] == 0) {
        p[u] = v;
        dfs(u, p, graypath, cycles, res, outs, color);
      }
      if (color[u] == 1) {
        if (p[v] != u) {
          Array<long long int> cycle;
          bool now = false;
          for (long long int i = 0; i < graypath.size(); i++) {
            if (graypath[i] == u) {
              now = true;
            }
            if (now) {
              cycle.add(graypath[i]);
            }
            if (graypath[i] == v) {
              now = false;
            }
          }
          cycles = cycle;
        }
      }
    }
    graypath.pop_back();
    color[v] = 2;
    outs.add(v);
  }
  Array<long long int> dfs(long long int number) {
    long long int* color = new long long int[n]();
    long long int* p = new long long int[n]();
    Array<long long int> res;
    Array<long long int> outs;
    Array<long long int> cycles;
    vector<long long int> path;
    dfs(number, p, path, cycles, res, outs, color);
    return res;
  }
  Array<Array<long long int> > findConnectedComponents() {
    Array<Array<long long int> > res;
    long long int* array = new long long int[n]();
    for (long long int i = 0; i < n; i++) {
      if (!array[i]) {
        Array<long long int> component = dfs(i);
        for (long long int j = 0; j < component.size; j++) {
          array[component[j]] = i + 1;
        }
        res.add(component);
      }
    }
    return res;
  }
  void shortestPath(Array<long long int>& p, long long int from,
                    long long int to, Array<long long int>& res) {
    if (from == to) {
      res.add(from);
    } else {
      res.add(to);
      long long int newTo = p[to];
      shortestPath(p, from, newTo, res);
    }
  }
  Array<long long int> shortestPath(Array<long long int>& p, long long int from,
                                    long long int to) {
    Array<long long int> res;
    shortestPath(p, from, to, res);
    reverse(res.begin(), res.end());
    return res;
  }
  Array<long long int> bfsPath(long long int s, long long int t) {
    Array<long long int> p(n);
    Array<long long int> dists(n);
    bfs(p, dists, s);
    for (long long int i = 0; i < n; i++) {
      dists[i] = -1;
    }
    return shortestPath(p, s, t);
  }
  Array<long long int> bfsDists(long long int root) {
    Array<long long int> p(n);
    Array<long long int> dists(n);
    for (long long int i = 0; i < n; i++) {
      dists[i] = -1;
    }
    bfs(p, dists, root);
    return dists;
  }
  Array<long long int> findCycles() {
    long long int* color = new long long int[n]();
    long long int* p = new long long int[n]();
    Array<long long int> res;
    Array<long long int> outs;
    Array<long long int> cycles;
    vector<long long int> graypath;
    dfs(0, p, graypath, cycles, res, outs, color);
    return cycles;
  }
  void bfs(Array<long long int>& p, Array<long long int>& dists,
           long long int root) {
    queue<long long int> q;
    q.push(root);
    long long int* visited = new long long int[this->n]();
    visited[root] = true;
    dists[root] = 0;
    while (!q.empty()) {
      long long int v = q.front();
      q.pop();
      for (long long int i = 0; i < adj[v].size(); i++) {
        long long int u = adj[v][i];
        if (!visited[u]) {
          visited[u] = true;
          dists[u] = dists[v] + 1;
          p[u] = v;
          q.push(u);
        }
      }
    }
  }
  Array<long long int> toposort() {
    n++;
    vector<long long int> newAdj;
    adj[n] = newAdj;
    for (long long int i = 0; i < n - 1; i++) {
      this->add(n - 1, i);
    }
    Array<long long int> res;
    Array<long long int> outs;
    vector<long long int> path;
    Array<long long int> cycles;
    long long int* color = new long long int[n]();
    long long int* pr = new long long int[n]();
    dfs(n - 1, pr, path, cycles, res, outs, color);
    n--;
    Array<long long int> p(outs.size - 1);
    for (long long int i = 0; i < outs.size - 1; i++) {
      p[i] = outs[i];
    }
    reverse(p.begin(), p.end());
    Array<long long int> r(p.size);
    for (long long int i = 0; i < p.size; i++) {
      r[p[i]] = i;
    }
    for (long long int i = 0; i < n; i++) {
      for (long long int j = 0; j < adj[i].size(); j++) {
        long long int v = adj[i][j];
        if (r[i] >= r[v]) {
          Array<long long int> sh(0);
          return sh;
        }
      }
    }
    return p;
  }
  long long int INF = 1000000000;
  long long int INFP = 1000000000 / 2;
  void Dijkstra(Array<long long int>& p, Array<long long int>& d,
                long long int s) {
    for (long long int i = 0; i < n; i++) {
      d.add(this->INF);
    }
    d[s] = 0;
    for (long long int i = 0; i < n; i++) {
      p.add(this->INF);
    }
    p[s] = s;
    set<pair<long long int, long long int> > q;
    q.insert(make_pair(d[s], s));
    while (!q.empty()) {
      long long int v = q.begin()->second;
      q.erase(q.begin());
      for (size_t j = 0; j < adj[v].size(); ++j) {
        long long int to = adj[v][j];
        long long int len = w[v][j];
        if (d[v] + len < d[to]) {
          q.erase(make_pair(d[to], to));
          d[to] = d[v] + len;
          p[to] = v;
          q.insert(make_pair(d[to], to));
        }
      }
    }
  }
};
long long int clp2(long long int x) {
  x--;
  for (long long int p = 1; p < 32; p <<= 1) x |= (x >> p);
  return ++x;
}
void fillArray(Array<long long int>& a) {
  long long int need = clp2(a.size);
  for (long long int i = a.size; i < need; i++) {
    a.add(0);
  }
}
istream& operator>>(istream& in, Graph& g) {
  long long int n;
  long long int m;
  cin >> n >> m;
  Graph graph(n);
  graph.isDirected = g.isDirected;
  graph.isWeighted = g.isWeighted;
  for (long long int i = 0; i < m; i++) {
    long long int x;
    long long int y;
    cin >> x >> y;
    if (!graph.isWeighted) {
      graph.add(x - 1, y - 1);
    } else {
      long long int w;
      cin >> w;
      graph.addWeighted(x - 1, y - 1, w);
    }
  }
  g = graph;
  return in;
}
ostream& operator<<(ostream& out, Graph& g) {
  for (long long int i = 0; i < g.n; i++) {
    out << i << " {";
    for (long long int j = 0; j < g.adj[i].size(); j++) {
      if (j != g.adj[i].size() - 1) {
        out << g.adj[i][j] << " ";
      } else {
        out << g.adj[i][j];
      }
    }
    out << "}";
    out << endl;
  }
  return out;
}
int main(void) {
  RANDOM = 0;
  srand(time(0));
  long long int a;
  long long int b;
  cin >> a >> b;
  long long int maxCom = min(a, b);
  long long int maxRes = 0;
  for (long long int f = 0; f <= maxCom; f++) {
    long long int o1 = f;
    long long int n1 = 2 * f;
    long long int orest = a - o1;
    long long int nrest = b - n1;
    if (orest >= 0 && nrest >= 0) {
      long long int s = min(orest / 2, nrest);
      long long int total = s + f;
      if (total > maxRes) {
        maxRes = total;
      }
    }
  }
  cout << maxRes;
}

```