算法练习专栏——Codeforces——Codeforces Round 946 (Div. 3)

B. Symmetric Encoding

原题

Polycarp has a string $s$, which consists of lowercase Latin letters. He encodes this string using the following algorithm:

  • first, he constructs a new auxiliary string $r$, which consists of all distinct letters of the string $s$, written in alphabetical order;
  • then the encoding happens as follows: each character in the string $s$ is replaced by its symmetric character from the string $r$ (the first character of the string $r$ will be replaced by the last, the second by the second from the end, and so on).

For example, encoding the string $s$=“codeforces” happens as follows:

  • the string $r$ is obtained as “cdefors”;
  • the first character $s_1$=‘c’ is replaced by ‘s’;
  • the second character $s_2$=‘o’ is replaced by ‘e’;
  • the third character $s_3$=‘d’ is replaced by ‘r’;
  • …
  • the last character $s_{10}$=‘s’ is replaced by ‘c’.

The string $r$ and replacements for $s$=“codeforces”.

Thus, the result of encoding the string $s$=“codeforces” is the string “serofedsoc”.

Write a program that performs decoding — that is, restores the original string $s$ from the encoding result.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the string $b$.

The second line of each test case contains a string $b$ of length $n$, consisting of lowercase Latin letters — the result of encoding the original string $s$.

It is guaranteed that the sum of the values of $n$ over all test cases in the test does not exceed $2 \cdot 10^5$.

Output

For each test case, output the string $s$ from which the encoding result $b$ was obtained.

Example

input

1
2
3
4
5
6
7
8
9
10
11
5
10
serofedsoc
3
ttf
9
tlrhgmaoi
1
w
15
hnndledmnhlttin

output

1
2
3
4
5
codeforces
fft
algorithm
w
meetinthemiddle

翻译

Polycarp 有一个字符串 $s$ ，由小写拉丁字母组成。他使用以下算法对该字符串进行编码：

  • 首先，他构造一个新的辅助字符串 $r$ ，它由字符串 $s$ 的所有不同字母组成，按字母顺序书写；
  • 然后编码如下：字符串 $s$ 中的每个字符都被字符串 $r$ 中的对称字符替换(字符串 $r$ 的第一个字符将被最后一个字符替换，第二个字符将被第二个字符替换)从最后开始，依此类推）。

例如，对字符串 $s$ =“codeforces” 进行编码如下：

  • 字符串 $r$ 作为“cdefors”获得；
  • 第一个字符 $s _ 1$ =‘c’被’s’替换；
  • 第二个字符 $s _ 2$ =‘o’ 替换为 ‘e’；
  • 第三个字符 $s _ 3$ =‘d’被’r’替换；
  • …
  • 最后一个字符 $s _ {10}$ =‘s’ 被替换为 ‘c’。

字符串 $r$ 和 $s$ =“codeforces” 的替换。

因此，对字符串 $s$ =“codeforces” 进行编码的结果是字符串“serofedsoc”。

编写一个执行解码的程序——即从编码结果中恢复原始字符串 $s$ 。

输入

第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) - 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ( $1 \le n \le 2 \cdot 10^5$ ) - 字符串 $b$ 的长度。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $b$ ，由小写拉丁字母组成——原始字符串 $s$ 编码的结果。

保证测试中所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$ 。

输出

对于每个测试用例，输出字符串 $s$ ，从中获得编码结果 $b$ 。

Example

input

1
2
3
4
5
6
7
8
9
10
11
5
10
serofedsoc
3
ttf
9
tlrhgmaoi
1
w
15
hnndledmnhlttin

output

1
2
3
4
5
codeforces
fft
algorithm
w
meetinthemiddle

思路

​ 就是模拟题,理解题意即可解答.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>
#include <iomanip>

// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) printf("%d",  int(x))
#define re return 0
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
typedef double db;


const int INF = 1e9;
const int N = 2e5 + 10;
bool st[30];
char s[N];
int s0[30];
map<char, char> mp;

void solve() {
    memset(st, false, sizeof st);
    int n;
    
    mp.clear();
    scanf("%d %s", &n, s + 1);
    mp.clear();
    
    fore (i, 1, n) {
        st[s[i] - 'a'] = true;  
    }
    int k = 0;
    
    fore (i, 0, 25) {
        if (st[i]) s0[k++] = 'a' + i;
    }
    
    fore (i, 0, k - 1) {
        mp[s0[k - i - 1]] = s0[i];
        mp[s0[i]] = s0[k - i - 1];
    } 
    
    
    fore (i, 1, n) {
        s[i] = mp[s[i]];
        cout << s[i];
    }
    
    // fore (i, 1, n) printf("%c ", s[i]);
    puts("");
}

int main()
{
    // IOS;
    int _ = 1;
    cin >> _;
    while(_--) {
        solve();
    }
    
    re;
}

C. Beautiful Triple Pairs

原题

Polycarp was given an array $a$ of $n$ integers. He really likes triples of numbers, so for each $j$ ($1 \le j \le n - 2$) he wrote down a triple of elements $[a_j, a_{j + 1}, a_{j + 2}]$.

Polycarp considers a pair of triples $b$ and $c$ beautiful if they differ in exactly one position, that is, one of the following conditions is satisfied:

  • $b_1 \ne c_1$ and $b_2 = c_2$ and $b_3 = c_3$;
  • $b_1 = c_1$ and $b_2 \ne c_2$ and $b_3 = c_3$;
  • $b_1 = c_1$ and $b_2 = c_2$ and $b_3 \ne c_3$.

Find the number of beautiful pairs of triples among the written triples $[a_j, a_{j + 1}, a_{j + 2}]$.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — the elements of the array.

It is guaranteed that the sum of the values of $n$ for all test cases in the test does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer — the number of beautiful pairs of triples among the pairs of the form $[a_j, a_{j + 1}, a_{j + 2}]$.

Note that the answer may not fit into 32-bit data types.

Example

input

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

output

1
2
3
4
5
6
7
8
2
0
3
1
8
4
3
2

Note

In the first example, $a = [3, 2, 2, 2, 3]$, Polycarp will write the following triples:

  1. $[3, 2, 2]$;
  2. $[2, 2, 2]$;
  3. $[2, 2, 3]$.

The beautiful pairs are triple $1$ with triple $2$ and triple $2$ with triple $3$.

In the third example, $a = [1, 2, 3, 2, 2, 3, 4, 2]$, Polycarp will write the following triples:

  1. $[1, 2, 3]$;
  2. $[2, 3, 2]$;
  3. $[3, 2, 2]$;
  4. $[2, 2, 3]$;
  5. $[2, 3, 4]$;
  6. $[3, 4, 2]$;

The beautiful pairs are triple $1$ with triple $4$, triple $2$ with triple $5$, and triple $3$ with triple $6$.

翻译

Polycarp 被赋予了一个包含 $n$ 个整数的数组 $a$ 。他非常喜欢三元组的数字，因此对于每个 $j$ ( $1 \le j \le n - 2$ )，他写下了一个三元组的元素 $[a_j, a_{j + 1}, a_{j + 2}]$ 。

Polycarp 认为一对三元组 $b$ 和 $c$ 是美丽的，如果它们恰好在一个位置上不同，即满足以下条件之一：

  • $b_1 \ne c_1$ 、 $b_2 = c_2$ 和 $b_3 = c_3$ ；
  • $b_1 = c_1$ 和 $b_2 \ne c_2$ 和 $b_3 = c_3$ ；
  • $b_1 = c_1$ 、 $b_2 = c_2$ 和 $b_3 \ne c_3$ 。

找出书面三元组中漂亮的三元组对的数量 $[a_j, a_{j + 1}, a_{j + 2}]$ 。

输入

第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) - 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ( $3 \le n \le 2 \cdot 10^5$ ) - 数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 整数 $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^6$ ) - 数组的元素。

保证测试中所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$ 。

输出

对于每个测试用例，输出一个整数 - $[a_j, a_{j + 1}, a_{j + 2}]$ 形式的对中美丽的三元组对的数量。

请注意，答案可能不适合 32 位数据类型。

Example

input

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

output

1
2
3
4
5
6
7
8
2
0
3
1
8
4
3
2

笔记

在第一个示例 $a = [3, 2, 2, 2, 3]$ 中，Polycarp 将编写以下三元组：

  1. $[3, 2, 2]$ ；
  2. $[2, 2, 2]$ ；
  3. $[2, 2, 3]$ 。

美丽的对是三元组 $1$ 与三元组 $2$ 和三元组 $2$ 与三元组 $3$ 。

在第三个示例 $a = [1, 2, 3, 2, 2, 3, 4, 2]$ 中，Polycarp 将编写以下三元组：

  1. $[1, 2, 3]$ ；
  2. $[2, 3, 2]$ ；
  3. $[3, 2, 2]$ ；
  4. $[2, 2, 3]$ ；
  5. $[2, 3, 4]$ ；
  6. $[3, 4, 2]$ ；

美丽的对是三元组 $1$ 与三元组 $4$ ，三元组 $2$ 与三元组 $5$ ，以及三元组 $3$ 与三元组 $6$ 。

思路

​ 这道题目运用了一点哈希的思想 + 容斥原理的知识.总的思路就是这个样子:

​ 首先记录一下所有$a_j,a_{j + 1}$ , $a_{j},a_{j + 2}$ $a_{j + 1},a_{j + 2}$组合的数量,外加$a_{j},a_{j + 1},a{j + 2}$的数量.我们在这里设这些组合的数量为val,最后我们在计算的时候只需要依次计算res += val * (val - 1) / 2,将所有的组合的组数计算出来即可.(意思是如1 2 3 | 1 2 4 |1 2 5,这里我们计算1 2 组合的元组数量是不是就是2 + 1计算即可,实际上就是计算数组的前n项和),当然这里也可能会出现元组重复的情况,这样的话实际上也就是需要减去相同元组之间组数的组成数量,n * (n - 1) / 2,同时还需要 X 3,因为相同元组包括了[aj, aj + 1], [aj, aj + 2], [aj + 1, aj + 2] 这三个部分,需要同时减去这三者的公共部分

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>
#include <iomanip>

#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) prLLf("%lf", double(x))
#define pif(x) prLLf("%d ",  int(x))
#define scf(x) prLLf("%d", int(x))
#define re return 0
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed

using namespace std;
typedef long long LL;
typedef pair<LL, LL> PII;
typedef double db;


const LL INF = 1e9;
const LL N = 2e5 + 10;

void solve() {
    LL mx = 2e6;
    LL n;
    cin >> n;
    LL a[n];
    for(LL i = 0;i < n; ++i) cin >> a[i];
    map<LL,LL> u1, u2, u3, u;
    for(LL i = 0;i < n - 2; ++i)
    {
        u1[a[i] * mx + a[i + 1]]++;
        u2[a[i] * mx+a[i + 2]]++;
        u3[a[i + 1] * mx + a[i + 2]]++;
        u[a[i] * mx * mx + a[i + 1] * mx + a[i + 2]]++;
    }
    LL res = 0;
    for(auto [key,val]:u1) res += val * (val - 1) / 2;
    
    for(auto [key,val]:u2) res += val * (val - 1) / 2;
    
    for(auto [key,val]:u3) res += val * (val - 1) / 2;
    
    // 这里是排除所有相同的情况(属于容斥原理的思想)
    for(auto [key,val]:u) res -= 3 * val * (val - 1) / 2;
    cout << res << ed;
}

int main()
{
    IOS;
    LL _ = 1;
    cin >> _;
    while(_--) {
        solve();
    }
    re;   
}

D. Ingenuity-2

原题

Let’s imagine the surface of Mars as an infinite coordinate plane. Initially, the rover Perseverance-2 and the helicopter Ingenuity-2 are located at the point with coordinates $(0, 0)$. A set of instructions $s$ consisting of $n$ instructions of the following types was specially developed for them:

  • N: move one meter north (from point $(x, y)$ to $(x, y + 1)$);
  • S: move one meter south (from point $(x, y)$ to $(x, y - 1)$);
  • E: move one meter east (from point $(x, y)$ to $(x + 1, y)$);
  • W: move one meter west (from point $(x, y)$ to $(x - 1, y)$).

Each instruction must be executed either by the rover or by the helicopter. Moreover, each device must execute at least one instruction. Your task is to distribute the instructions in such a way that after executing all $n$ instructions, the helicopter and the rover end up at the same point, or determine that this is impossible.

Input

The first line of input contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of instructions.

The second line of each test case contains a string $s$ of length $n$ consisting of the characters ‘N’, ‘S’, ‘E’, ‘W’ — the sequence of instructions.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10 ^ 5$.

Output

For each test case, if the required distribution of instructions exists, output a string $p$ of length $n$ consisting of the characters ‘R’, ‘H’. If the $i$-th operation should be executed by the rover, then $p_i=\text{R}$, if the $i$-th operation should be executed by the helicopter, then $p_i=\text{H}$. If there are multiple solutions, output any of them.

Otherwise, output NO.

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
10
6
NENSNE
3
WWW
6
NESSWS
2
SN
2
WE
4
SSNN
4
WESN
2
SS
4
EWNN
4
WEWE

output

1
2
3
4
5
6
7
8
9
10
RRHRRH
NO
HRRHRH
NO
NO
RHRH
RRHH
RH
RRRH
RRHH

Note

Let’s consider the first example: the string $S = \texttt{NENSNE}$. One of the possible solutions, shown in the figure below, is $p = \texttt{RRHRRH}$, using which both the rover and the helicopter will end up one meter north and one meter east.

For WWW, the solution is impossible.

翻译

让我们将火星表面想象为一个无限的坐标平面。最初，Perseverance-2 漫游车和 Ingenuity-2 直升机位于坐标为 $(0, 0)$ 的点。专门为他们开发了由以下类型的 $n$ 指令组成的一组指令 $s$ ：

  • N：向北移动一米(从点 $(x, y)$ 到 $(x, y + 1)$ )；
  • S：向南移动一米(从点 $(x, y)$ 到 $(x, y - 1)$ )；
  • E：向东移动一米(从点 $(x, y)$ 到 $(x + 1, y)$ )；
  • W：向西移动一米(从点 $(x, y)$ 到 $(x - 1, y)$ )。

每条指令必须由流动站或直升机执行。此外，每个设备必须执行至少一条指令。你的任务是以这样的方式分发指令，使得在执行所有 $n$ 指令后，直升机和流动站最终到达同一点，或者确定这是不可能的。

输入

输入的第一行包含 $t$ ( $1 \leq t \leq 10^4$ ) - 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ( $1 \le n \le 2 \cdot 10^5$ ) - 指令数。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$ ，由字符“N”、“S”、“E”、“W”(指令序列)组成。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10 ^ 5$ 。

输出

对于每个测试用例，如果存在所需的指令分布，则输出长度为 $n$ 的字符串 $p$ ，由字符“R”、“H”组成。如果第 $i$ 个操作应由流动站执行，则为 $p _ i=\text{R}$ ，如果第 $i$ 个操作应由直升机执行，则为 $p _ i=\text{H}$ 。如果有多个解，输出任意一个。

否则输出NO。

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
10
6
NENSNE
3
WWW
6
NESSWS
2
SN
2
WE
4
SSNN
4
WESN
2
SS
4
EWNN
4
WEWE

output

1
2
3
4
5
6
7
8
9
10
RRHRRH
NO
HRRHRH
NO
NO
RHRH
RRHH
RH
RRRH
RRHH

笔记

让我们考虑第一个示例：字符串 $S = \texttt{NENSNE}$ 。如下图所示，其中一种可能的解决方案是 $p = \texttt{RRHRRH}$ ，使用该解决方案，流动站和直升机最终都会向北一米，向东一米。

对于WWW来说，解决方案是不可能的。

思路

​

代码

1

E. Money Buys Happiness

原题

Being a physicist, Charlie likes to plan his life in simple and precise terms.

For the next $m$ months, starting with no money, Charlie will work hard and earn $x$ pounds per month. For the $i$-th month $(1 \le i \le m)$, there’ll be a single opportunity of paying cost $c_i$ pounds to obtain happiness $h_i$.

Borrowing is not allowed. Money earned in the $i$-th month can only be spent in a later $j$-th month ($j>i$).

Since physicists don’t code, help Charlie find the maximum obtainable sum of happiness.

Input

The first line of input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains two integers, $m$ and $x$ ($1 \le m \le 50$, $1 \le x \le 10^8$) — the total number of months and the monthly salary.

The $i$-th of the following $m$ lines contains two integers, $c_i$ and $h_i$ ($0 \le c_i \le 10^8$, $1 \le h_i \le 10^3$) — the cost and happiness on offer for the $i$-th month. Note that some happiness may be free ($c_i=0$ for some $i$’s).

It is guaranteed that the sum of $\sum_i h_i$ over all test cases does not exceed $10^5$.

Output

For each test case, print a single integer, the maximum sum of happiness Charlie could obtain.

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
7
1 10
1 5
2 80
0 10
200 100
3 100
70 100
100 200
150 150
5 8
3 1
5 3
3 4
1 5
5 3
2 5
1 5
2 1
5 3
2 5
2 4
4 1
5 1
3 4
5 2
2 1
1 2
3 5
3 2
3 2

output

1
2
3
4
5
6
7
0
10
200
15
1
9
9

Note

In the first test case, Charlie only gets paid at the end of the month, so is unable to afford anything.

In the second test case, Charlie obtains the free happiness in the first month.

In the third test case, it’s optimal for Charlie to buy happiness in the second month. Even with money left at the end, Charlie could not go back in time to obtain the happiness on offer in the first month.

翻译

作为一名物理学家，查理喜欢用简单而精确的方式规划自己的生活。

在接下来的 $m$ 个月里，从没有钱开始，查理将努力工作，每月赚取 $x$ 英镑。在第 $i$ 个月 $(1 \le i \le m)$ ，将有一次机会支付成本 $c_i$ 英镑来获得幸福 $h_i$ 。

不允许借款。第 $i$ 个月赚取的钱只能在稍后的第 $j$ 个月 ( $j>i$ ) 中支出。

由于物理学家不会编码，请帮助查理找到可获得的最大幸福感。

输入

输入的第一行包含一个整数 $t$ ( $1 \le t \le 1000$ ) - 测试用例的数量。

每个测试用例的第一行包含两个整数： $m$ 和 $x$ （ $1 \le m \le 50$ 、 $1 \le x \le 10^8$ ）——总月数和月薪。

以下 $m$ 行的第 $i$ -th 行包含两个整数： $c_i$ 和 $h_i$ （ $0 \le c_i \le 10^8$ 、 $1 \le h_i \le 10^3$ ） - 第 $i$ -th 个月的成本和幸福感。请注意，有些幸福可能是免费的（对于某些 $i$ 而言， $c_i=0$ ）。

保证所有测试用例的 $\sum_i h_i$ 之和不超过 $10^5$ 。

输出

对于每个测试用例，打印一个整数，即查理可以获得的最大幸福感。

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
7
1 10
1 5
2 80
0 10
200 100
3 100
70 100
100 200
150 150
5 8
3 1
5 3
3 4
1 5
5 3
2 5
1 5
2 1
5 3
2 5
2 4
4 1
5 1
3 4
5 2
2 1
1 2
3 5
3 2
3 2

output

1
2
3
4
5
6
7
0
10
200
15
1
9
9

笔记

在第一个测试案例中，查理只能在月底收到工资，因此无法承担任何费用。

在第二个测试案例中，查理在第一个月获得了免费的幸福。

在第三个测试案例中，查理在第二个月购买幸福是最佳的。即使最后剩下钱，查理也无法回到过去，获得第一个月的幸福。

思路

​

代码

1