← 返回题目列表

AtCoder · arc224_d

D. 所有配对的焦虑

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有 N 卡片,已编号 1 通过 N。最初,任何卡片上都没有写任何内容。

您可以在每张卡上写入零个或多个正整数。

写入正整数的成本 k 一次等于十进制表示的位数 k.

判断是否可以满足以下条件。如果可以,输出所需的最小总成本;如果不可能,则输出 -1.

  • 对于每对正整数 (x,y) 满意 1 \leq x < y \leq K,存在一张卡片恰好包含以下之一 x 和 y.

T 给出了测试用例;解决它们中的每一个。 每个输入中的

约束

  • 1 \leq T \leq 10^5
  • 1 \leq N \leq 10^6
  • 2 \leq K \leq 10^6
  • 总和 N 最多为 10^6.
  • 总和 K 最多为 10^6.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出,其中 \mathrm{case}_i 表示 i-第一个测试用例:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个测试用例均按以下格式给出:

N K

输出

输出 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。


示例输入 1

4
3 5
100 25
5 1225
180 998244

示例输出 1

5
39
-1
17655598

此输入包含四个测试用例。

对于第一个测试用例,编写如下满足条件,总成本为 卡上的 5.

  • 写 单元格中的 1, 5 卡上 1.
  • 写 单元格中的 2, 5 卡上 2.
  • 写 单元格中的 3 卡上 3.

对于第二个测试用例,满足条件所需的最小总成本为 39.

对于第三个测试用例,不可能满足条件,因此输出 -1.

对于第四个测试用例,满足条件所需的最小总成本为 17655598.