問題文
伊织酱的最近兴趣是金字塔。
Iori-chan 的半径为 我有大量 1 球形石头,即 L \times (L+1) \times (L+2) / 6 件 顺时针或逆时针围绕 1 侧面是 L 我试图通过将它们排列成正四面体的形式来制作类似金字塔的东西。以便可以稳定地放置在办公桌上, 我正在尝试将它们排列在带有L \times (L+1) / 2 圆孔的木板上。然而,他在钻孔时犯了错误,有些孔无法放入石头。如果伊织按照排列正四面体的方式排列石头,她能放置多少颗石头?然而,“与将石头排列成正四面体时相同的方式排列石头”是指以下排列。
- 将石头排列成规则的四面体图案时,从底部开始 i (1 ≦ i ≦ L) 一步,从后面 j (1 ≦ j ≦ L-i+1) 列,从左起 k (1 ≦ k ≦ j) 定位第二个棋子应该放置的位置。 我们称之为 (i,j,k) 。然而,从下面看 1 从后面的台阶 x (1 ≦ x ≦ L) 在栏中 我将其放置在 x 石头排成一排。
- 首先从底部开始 1 在所有已成功钻孔且可以放置石子的行位置放置石子。
- 从下面 2 从第一行开始 L 行位置 (i,j,k) ,位置 也位于 (i-1,j,k) 也位于 (i-1,j+1,k) 也位于 (i-1,j+1,k+1) 将棋子放在有棋子的位置,重复此操作,直到没有更多的地方可以放置棋子。 在
入力
输入是按以下格式从标准输入给出的。
L N A_1 B_1 A_2 B_2 : A_N B_N
- 1 行中,2 整数 L (2 ≦ L ≦ 10^5), N (0 ≦ N ≦ Min(10^5, L \times (L+1) / 2)) 用空格分隔。这是 对于1 侧面是 L 石头计划排列成正四面体形状,破洞的位置是 这意味着有 N 。
- 2 从线 N 行提供有关钻孔失败位置的信息。其中 给出了 i (1 ≦ i ≦ N) 行中,2 整数 A_i (1 ≦ A_i ≦ L), B_i (1 ≦ B_i ≦ A_i) 。这是从后面看 A_i 列,从左起 B_i 表示钻第二个孔失败。然而,同一位置的信息是 保证给予不超过 2 次。
部分点
针对此问题设置了部分分数。
- N ≦ 20 的数据集 如果您正确回答 1 ,58 点。 如果您正确回答了所有满足
- 如果所有测试用例都回答正确,将给予满分。
出力
八神酱放置的棋子数量 在 1 行输出。在输出末尾插入换行符。
入力例1
3 1 2 1
出力例1
6
位置 (1,1,1)、位置 (1,2,2)、位置 (1,3,1)、位置 (1,3,2)、位置 (1,3,3)、位置 (2,2,2) 可以得到第 6 您可以在该位置放置石头。
入力例2
100000 0
出力例2
166671666700000
这样,要小心,因为有可能你实际上并没有打孔失败。
入力例3
6 4 3 2 6 6 5 2 3 3
出力例3
25