开始搞ACM

上个月开始搞ACM(ICPC),虽然只是做一些水题。一道题苦想半天调试N遍最后AC,这感觉 特别爽哟。

随手拿最近的一些水题放上来吧,当做纪念,可能几年后我成为了大神,人们来嘲笑我说,这么烂的代码竟然是他曾经写的。


Codeforces Round #237 (Div. 2) - Valera and Fruits

Description

Valera loves his garden, where n fruit trees grow.

This year he will enjoy a great harvest! On the i-th tree bi fruit grow, they will ripen on a day number ai. Unfortunately, the fruit on the tree get withered, so they can only be collected on day ai and day ai + 1 (all fruits that are not collected in these two days, become unfit to eat).

Valera is not very fast, but there are some positive points. Valera is ready to work every day. In one day, Valera can collect no more thanv fruits. The fruits may be either from the same tree, or from different ones. What is the maximum amount of fruit Valera can collect for all time, if he operates optimally well?


Input

The first line contains two space-separated integers n and v(1 ≤ n, v ≤ 3000) — the number of fruit trees in the garden and the number of fruits that Valera can collect in a day.

Next n lines contain the description of trees in the garden. The i-th line contains two space-separated integers ai and bi(1 ≤ ai, bi ≤ 3000) — the day the fruits ripen on the i-th tree and the number of fruits on the i-th tree.


Output

Print a single integer — the maximum number of fruit that Valera can collect.


Sample Input

Input

2 3
1 5
2 3

Output

8

Input

5 10
3 20
2 20
1 20
4 20
5 20

Output

60



Hint

In the first sample, in order to obtain the optimal answer, you should act as follows.

  • On the first day collect 3 fruits from the 1-st tree.
  • On the second day collect 1 fruit from the 2-nd tree and 2 fruits from the 1-st tree.
  • On the third day collect the remaining fruits from the 2-nd tree.
    In the second sample, you can only collect 60 fruits, the remaining fruit will simply wither.



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
#include<stdio.h>
#include<string.h>
#include <algorithm>
using namespace std;
int main()
{

long int n,v,vv,a[3008],b[3008] ,i,ii,t,o,y,iy;
while (scanf("%d%d", &n, &v) != EOF)
{
o = 0; vv = v; y = 0;
for (i = 0; i < n; i++)
{
cin >> a[i]>>b[i];
}
for (i = 0; i < n; i++)
for (ii = i + 1; ii < n; ii++)
{
if (a[i]>a[ii])
{
t = a[i]; a[i] = a[ii]; a[ii] = t;
t = b[i]; b[i] = b[ii]; b[ii] = t;
}

}

//
//
//

for (i = 0; i < n; i++)
{
if (i != 0)
{
if (a[i] != a[i - 1]) { v = vv; }

}
if (v != 0 && i != 0)
{
for (iy = y; iy < i; iy++)
{
if (b[iy] != 0)
{
if (v <= b[iy])
{
o += v; b[iy] -= v; v = 0;
}
else { o += b[iy]; v -= b[iy]; b[iy] = 0; }
}
}
}
if (a[i] - a[i - 1] > 1) v = vv;
if (v != 0)
{
if (v <= b[i])
{
o += v; b[i] -= v; v = 0;
}
else { o += b[i]; v -= b[i]; b[i] = 0; }
}
if (a[i - 1] != a[i]&&i!=0) y = i;

}

//
//
//

v = vv;

for (iy = y; iy < i; iy++)
{
if (b[iy] != 0)
{
if (v <= b[iy])
{
o += v; b[iy] -= v; v = 0;
}
else { o += b[iy]; v -= b[iy]; b[iy] = 0; }
}
}

cout << o << endl;

}
return(0);
}

 


Codefoces 436B-Om Nom and Spiders

Description

Om Nom really likes candies and doesn’t like spiders as they frequently steal candies. One day Om Nom fancied a walk in a park. Unfortunately, the park has some spiders and Om Nom doesn’t want to see them at all.

The park can be represented as a rectangular n × m field. The park has k spiders, each spider at time 0 is at some cell of the field. The spiders move all the time, and each spider always moves in one of the four directions (left, right, down, up). In a unit of time, a spider crawls from his cell to the side-adjacent cell in the corresponding direction. If there is no cell in the given direction, then the spider leaves the park. The spiders do not interfere with each other as they move. Specifically, one cell can have multiple spiders at the same time.

Om Nom isn’t yet sure where to start his walk from but he definitely wants:

  • to start walking at time 0 at an upper row cell of the field (it is guaranteed that the cells in this row do not contain any spiders);
  • to walk by moving down the field towards the lowest row (the walk ends when Om Nom leaves the boundaries of the park).
    We know that Om Nom moves by jumping. One jump takes one time unit and transports the little monster from his cell to either a side-adjacent cell on the lower row or outside the park boundaries.

Each time Om Nom lands in a cell he sees all the spiders that have come to that cell at this moment of time. Om Nom wants to choose the optimal cell to start the walk from. That’s why he wonders: for each possible starting cell, how many spiders will he see during the walk if he starts from this cell? Help him and calculate the required value for each possible starting cell.


Input

The first line contains three integers n, m, k(2 ≤ n, m ≤ 2000; 0 ≤ k ≤ m(n - 1)).

Each of the next n lines contains m characters — the description of the park. The characters in the i-th line describe the i-th row of the park field. If the character in the line equals “.“, that means that the corresponding cell of the field is empty; otherwise, the character in the line will equal one of the four characters: “L“ (meaning that this cell has a spider at time 0, moving left), “R“ (a spider moving right), “U“ (a spider moving up), “D“ (a spider moving down).

It is guaranteed that the first row doesn’t contain any spiders. It is guaranteed that the description of the field contains no extra characters. It is guaranteed that at time 0 the field contains exactly k spiders.


Output

Print m integers: the j-th integer must show the number of spiders Om Nom will see if he starts his walk from the j-th cell of the first row. The cells in any row of the field are numbered from left to right.


Sample Input

Input

3 3 4

R.L
R.U

Output

0 2 2

Input

2 2 2
..
RL

Output

1 1

Input

2 2 2
..
LR

Output

0 0

Input

3 4 8
….
RRLL
UUUU

Output

1 3 3 1

Input

2 2 2
..
UU

Output

0 0



Hint

Consider the first sample. The notes below show how the spider arrangement changes on the field over time:

…        …        ..U       …
R.L -> .*U -> L.R -> …
R.U .R. ..R …


Character “*“ represents a cell that contains two spiders at the same time.

  • If Om Nom starts from the first cell of the first row, he won’t see any spiders.
  • If he starts from the second cell, he will see two spiders at time 1.
  • If he starts from the third cell, he will see two spiders: one at time 1, the other one at time 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
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{

int n, m, k,i,j,fuck;
char in[2002][2002];
while (scanf("%d%d%d", &n,&m,&k) != EOF)
{
fuck = 0;
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
{
cin >> in[i][j];
}

for (j = 0; j < m; j++)
{
for (i = 1; i < n; i++)
{
if(i+i<n)if (in[i + i][j] == 'U')fuck++;
if (j - i>=0&&j-i<m)if (in[i][j - i] == 'R')fuck++;
if (j + i<m)if (in[i][j + i] == 'L')fuck++;
}
cout << fuck << ' '; fuck = 0;
}
cout<<endl;

}
return(0);
}

 


Codeforces 435B Pasha Maximizes

Description

Pasha has a positive integer a without leading zeroes. Today he decided that the number is too small and he should make it larger. Unfortunately, the only operation Pasha can do is to swap two adjacent decimal digits of the integer.

Help Pasha count the maximum number he can get if he has the time to make at most k swaps.


Input

The single line contains two integers a and k(1 ≤ a ≤ 1018; 0 ≤ k ≤ 100).


Output

Print the maximum number that Pasha can get if he makes at most k swaps.


Sample Input

Input

1990 1

Output

9190

Input

300 0

Output

300

Input

1034 2

Output

3104

Input

9090000078001234 6

Output

9907000008001234




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
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cstring>
using namespace std;
int main()
{

long int n, x[100008], y[100008], i = 0, j,xxx[100008],yyy[100008],u;
while (scanf("%d", &n) != EOF)
{

memset(xxx, 0, sizeof(xxx));
memset(yyy, 0, sizeof(yyy));
for (i = 0; i < n; i++)
{
cin >> x[i] >> y[i];

xxx[x[i]]++;
yyy[y[i]]++;
}
for (i = 0; i < n; i++)
{
u = n - xxx[y[i]] - 1;
cout << 2*n - 2 - u << ' ' << u << endl;
}

}
return(0);
}

 


codeforce 432B - Football Kit

Description

Consider a football tournament where n teams participate. Each team has two football kits: for home games, and for away games. The kit for home games of the i-th team has color xi and the kit for away games of this team has color yi(xi ≠ yi).

In the tournament, each team plays exactly one home game and exactly one away game with each other team (n(n - 1) games in total). The team, that plays the home game, traditionally plays in its home kit. The team that plays an away game plays in its away kit. However, if two teams has the kits of the same color, they cannot be distinguished. In this case the away team plays in its home kit.

Calculate how many games in the described tournament each team plays in its home kit and how many games it plays in its away kit.


Input

The first line contains a single integer n(2 ≤ n ≤ 105) — the number of teams. Next n lines contain the description of the teams. The i-th line contains two space-separated numbers xi, yi(1 ≤ xi, yi ≤ 105; xi ≠ yi) — the color numbers for the home and away kits of thei-th team.


Output

For each team, print on a single line two space-separated integers — the number of games this team is going to play in home and away kits, correspondingly. Print the answers for the teams in the order they appeared in the input.


Sample Input

Input

2
1 2
2 1

Output

2 0
2 0

Input

3
1 2
2 1
1 3

Output

3 1
4 0
2 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
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cstring>
using namespace std;
int main()
{

long int n, x[100008], y[100008], i = 0, j,xxx[100008],yyy[100008],u;
while (scanf("%d", &n) != EOF)
{

memset(xxx, 0, sizeof(xxx));
memset(yyy, 0, sizeof(yyy));
for (i = 0; i < n; i++)
{
cin >> x[i] >> y[i];

xxx[x[i]]++;
yyy[y[i]]++;
}
for (i = 0; i < n; i++)
{
u = n - xxx[y[i]] - 1;
cout << 2*n - 2 - u << ' ' << u << endl;
}

}
return(0);
}

 


Codeforces 431B Shower Line

Description

Many students live in a dormitory. A dormitory is a whole new world of funny amusements and possibilities but it does have its drawbacks.

There is only one shower and there are multiple students who wish to have a shower in the morning. That’s why every morning there is a line of five people in front of the dormitory shower door. As soon as the shower opens, the first person from the line enters the shower. After a while the first person leaves the shower and the next person enters the shower. The process continues until everybody in the line has a shower.

Having a shower takes some time, so the students in the line talk as they wait. At each moment of time the students talk in pairs: the(2i - 1)-th man in the line (for the current moment) talks with the (2i)-th one.

Let’s look at this process in more detail. Let’s number the people from 1 to 5. Let’s assume that the line initially looks as 23154 (person number 2 stands at the beginning of the line). Then, before the shower opens, 2 talks with 3, 1 talks with 5, 4 doesn’t talk with anyone. Then 2 enters the shower. While 2 has a shower, 3 and 1 talk, 5 and 4 talk too. Then, 3 enters the shower. While 3 has a shower, 1 and 5 talk, 4 doesn’t talk to anyone. Then 1 enters the shower and while he is there, 5 and 4 talk. Then 5 enters the shower, and then 4 enters the shower.

We know that if students i and j talk, then the i-th student’s happiness increases by gij and the j-th student’s happiness increases by gji. Your task is to find such initial order of students in the line that the total happiness of all students will be maximum in the end. Please note that some pair of students may have a talk several times. In the example above students 1 and 5 talk while they wait for the shower to open and while 3 has a shower.


Input

The input consists of five lines, each line contains five space-separated integers: the j-th number in the i-th line shows gij (0 ≤ gij ≤ 105). It is guaranteed that gii = 0 for all i.

Assume that the students are numbered from 1 to 5.


Output

Print a single integer — the maximum possible total happiness of the students.


Sample Input

Input

0 0 0 0 9
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
7 0 0 0 0

Output

32

Input

0 43 21 18 2
3 0 21 11 65
5 2 0 1 4
54 62 12 0 99
87 64 81 33 0

Output

620




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
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cstring>
using namespace std;
int main()
{

long int o[5][5], i,j, ii, iii, a, b, c, d, e,m=0,max=0;
while (scanf("%d", &o[0][0]) != EOF)
{
for (i = 0; i < 5; i++)
for (j = 0; j < 5; j++)
{
if (i == 0 && j == 0)j++;
cin >> o[i][j];
}
for (a = 0; a < 5; a++)
for (b = 0; b < 5;b++)
for (c = 0; c < 5; c++)
for (d = 0; d < 5; d++)
for (e = 0; e < 5; e++)
{
if(a!=b&&a!=c&&a!=d&&a!=e&&b!=c&&b!=d&&b!=e&&c!=d&&c!=e&&d!=e)
m = o[a][b] + o[b][a] + o[b][c] + o[c][b] + (o[c][d] + o[d][c]) * 2 + (o[d][e] + o[e][d]) * 2;
if (m>max) max = m;
}
cout << max<<endl;
}
return(0);
}