一只松鼠发现了一个藏有坚果的仓库。仓库包含 $N$ 行房间，编号为 $0$ 至 $N - 1$。索引为 $i$ 的行包含 $i + 1$ 个房间，编号为 $0$ 至 $i$。位于第 $i$ 行第 $j$ 列的房间包含 $A_{ij}$ 个坚果。

在这 $\frac{N \times (N + 1)}{2}$ 个房间中，坚果数量 $A_{ij}$ 互不相同，且取值在 $1$ 到 $\frac{N \times (N + 1)}{2}$ 之间。

正式地，仓库呈下三角矩阵（包含主对角线）的形状，其中每个元素代表该房间的坚果数量。该三角矩阵中的数字为 $1$ 到 $\frac{N \times (N + 1)}{2}$，且每个数字恰好出现一次。

例如，当 $N = 5$ 时，仓库将有 15 个房间，包含数字 $1$ 到 $15$。此类仓库的一个示例如下方的三角矩阵所示：

松鼠沿着主对角线移动。当它位于位置 $(i, i)$ 的房间时，它会在以 $(i, i)$ 为右上角、$(N - 1, 0)$ 为左下角的矩形区域内选择一个房间，并吃掉该房间中的坚果。在上述示例中，当松鼠位于位置 $(1, 1)$ 时，它可以选择吃掉标为红色的 8 个房间之一中的坚果。在走完主对角线上的所有房间，并恰好从 $N$ 个不同的房间中吃掉坚果后，松鼠满意地离开。

任务：给定 $N$ 以及对于所有满足 $0 \le i < N$ 且 $0 \le j \le i$ 的 $i, j$ 的 $A_{ij}$，求松鼠最多能吃到的坚果总数。

此外，对于访问的 $N$ 个房间中的每一个，求出松鼠吃掉的坚果数量。

实现细节

你需要实现以下函数：

void solve(int N, vector<vector<int>> A, long long& answer, vector<int>& solution)

函数参数：

输入数据：

• int N：仓库大小 / 行数
• vector<vector<int>> A：每个房间的坚果数量（更具体地说，在 $0 \le i < N$ 且 $0 \le j \le i$ 的 $A_{i,j}$ 中，你将找到第 $i$ 行第 $j$ 列位置的房间中的坚果数量）

输出数据：

• long long &answer：将包含松鼠在走完对角线上的所有 $N$ 个房间后能吃到的最大坚果数量。
• vector<int> &solution：一个向量，包含松鼠在每个房间吃掉的坚果数量。（更具体地说，对于 $0 \le i < N$，solution[i] 表示松鼠在位置 $(i, i)$ 的房间时吃掉的坚果数量）

注意：对于 $A$ 和 solution（在提示中写作 sol），索引均从 0 开始，且 solution 向量的大小应恰好为 $N$。

数据范围

• $1 \le N \le 2000$
• $1 \le A_{ij} \le \frac{N \times (N + 1)}{2}$

样例

输入样例 1

5
1
14 6
8 2 15
3 10 4 12
9 5 13 11 7

输出样例 1

64
14 10 15 12 13