class TrieNode {
    constructor() {
        this.children = new Array(26).fill(0);
        this.isEnd = false;
    }

    insert(word) {
        let node = this;
        for (let i = 0; i < word.length; i++) {
            const ch = word[i];
            const index = ch.charCodeAt() - 97;
            if (node.children[index] === 0) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    includes (word) {
        let node = this;
        for (let i = 0; i < word.length; i++) {
            const ch = word[i];
            const index = ch.charCodeAt() - 97;
            if (!node || !node.children[index]) {
                return false
            }
            node = node.children[index];
        }
        return node.isEnd
    }

    getChildren() {
        return this.children;
    }

    isEnd() {
        return this.isEnd;
    }
}

function lowbit (x) {
	return x & -x
}

function highbit(i) {
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    return i - (i >>> 1);
}

function bitMask (highbit, lowbit) {
   const i = ~0;
   return ~(i << highbit << 1) & (i << lowbit);
}

function bitCount(num) {
	let ans = 0
    for (let i = 0; i < 31; i ++) {
		if (num & (1 << i)) {
			ans ++
        }
    }
    return ans
}

function removeLastBit(num) {
   return num & (num - 1)
}

function appendLastBit(num) {
	return num | (num + 1)
}

function Bit (size) {
    this.tree = new Array(size + 1).fill(0)
};

Bit.prototype.lowbit = function (x) {
    return x & -x
}

Bit.prototype.add = function (index, num) {
    while (index && index < this.tree.length) {
        this.tree[index] += num
        index += this.lowbit(index)
    }
}

Bit.prototype.query = function (num) {
    let ans = 0
    while (num) {
        ans += this.tree[num]
        num -= this.lowbit(num)
    }
    return ans
}

function Node (start, end) {
    this.val = 0
    this.lazy = 0
    this.start = start
    this.end = end
    this.left = null
    this.right = null
}

function SegmentTree (start, end) {
    this.root = new Node(start, end)
}

SegmentTree.prototype.update = function (start, end) {
    this.updateNode(this.root, start, end)
}

SegmentTree.prototype.updateNode = function(node, start, end) {
    if (!node) {
        return
    }
    if (start > node.end || end < node.start) {
        return
    } else if (start <= node.start && end >= node.end) {
        node.lazy ++
        node.val ++
        return
    } else {
        this.pushdown(node);
        this.updateNode(node.left, start, end);
        this.updateNode(node.right, start, end);
        this.pushup(node);
    }
}

SegmentTree.prototype.pushdown = function (node) {
    if (!node) {
        return
    }
    const mid = Math.floor((node.start + node.end) / 2) 
    if (!node.left) {
        node.left = new Node(node.start, mid)
    }
    if (!node.right) {
        node.right = new Node(mid + 1, node.end)
    }
    node.left.lazy += node.lazy
    node.left.val += node.lazy
    node.right.lazy += node.lazy
    node.right.val += node.lazy
    node.lazy = 0
}

SegmentTree.prototype.pushup = function (node) {
    node.val = Math.max(node.left.val, node.right.val)
}

SegmentTree.prototype.query = function (start, end) {
    return this.queryNode(this.root, start, end)
}

SegmentTree.prototype.queryNode = function (node, start, end) {
    if (!node) {
        return 0;
    }
    if (start > node.end || end < node.start) {
        return 0;
    } else if (start <= node.start && end >= node.end) {
        return node.val;
    } else {
        this.pushdown(node);
        return Math.max(this.queryNode(node.left, start, end), this.queryNode(node.right, start, end));
    }
}

const isPrime = (n) => {
    if (n === 1) {
        return false;
    }
    for (let i = 2; i * i <= n; i++) {
        if (n % i === 0) {
            return false;
        }
    }
    return true;
}

class Heap {
  constructor (compare = (a, b) => a - b) {
    this.compare = compare
    this.list = []
  }

  get size () {
    return this.list.length
  }

  get top () {
    return this.list[0]
  }

  left (index) {
    return index * 2 + 1
  }

  right (index) {
    return index * 2 + 2
  }

  parent (index) {
    return (index - 1) >> 1
  }

  swap (index1, index2) {
    [this.list[index1], this.list[index2]] = [this.list[index2], this.list[index1]]
  }

  heapify (index) {
    const leftIndex = this.left(index)
    const rightIndex = this.right(index)
    let cur = index

    if (this.list[leftIndex] !== undefined && this.compare(this.list[cur], this.list[leftIndex]) > 0) {
      cur = leftIndex
    }
    if (this.list[rightIndex] !== undefined && this.compare(this.list[cur], this.list[rightIndex]) > 0) {
      cur = rightIndex
    } 

    if (cur !== index) {
      this.swap(cur, index)
      this.heapify(cur)
    }
  }

  insert(node) {
    this.list.push(node)
    let cur = this.size - 1
    let parentIndex = this.parent(cur)

    while (cur > 0 && this.compare(this.list[parentIndex], this.list[cur]) > 0) {
      this.swap(cur, parentIndex)
      cur = parentIndex
      parentIndex = this.parent(cur)
    }
  }

  remove() {
    this.swap(0, this.size - 1)
    const result = this.list.pop()
    this.heapify(0)
    return result
  }
}

Math.floor(n / divisor) * (divisor - 1) + (n % divisor)

const max = 1e6 + 33
const primes = []
const is_primes = new Array(max).fill(1)
for (let i = 2; i < max; i ++) {
    if (is_primes[i] === 1) {
        primes.push(i)
        for (let j = i * i; j < max; j += i) {
            is_primes[j] = 0
        }
    }
}

function getPrimeFactor(num) {
    res = []
    for (let i = 2; i < Math.sqrt(num) + 1; i ++) {
        let cnt = 0
        while ((num % i) === 0) {
            num /= i
            cnt += 1
        }
        if (cnt) {
            res.push([i, cnt])
        }
        if (i > num) {
            break
        }
    }
    if (num !== 1 || res.length === 0) {
        res.push([num, 1])
    }
    return res
}

const dirs = [
      [-1, 0],
      [0, -1],
      [1, 0],
      [0, 1]
  ]
  const visited = new Array(grid.length).fill(0)
      .map(() => new Array(grid[0].length).fill(0))
  let ans = 0
  
  function dfs (i, j) {
      if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) {
          return 0
      }
      if (grid[i][j] === 0 || visited[i][j]) {
          return 0
      }
      visited[i][j] = 1
      let cur = grid[i][j]
      for (const [di, dj] of dirs) {
          cur += dfs(i + di, j + dj, cur)
      }
      return cur
  }
  
  for (let i = 0; i < grid.length; i ++) {
      for (let j = 0; j < grid[0].length; j ++) {
          if (!visited[i][j]) {
              ans = Math.max(ans, dfs(i, j))
          }
      }
  }
  return ans