Problem Statement

Takahashi is at a fireworks festival venue. There are N firework launch points on a 2-dimensional plane, and the i-th firework is launched from coordinates (X_i, Y_i). If Takahashi can watch the i-th firework, he gains a satisfaction of P_i.

Takahashi is standing at the point with coordinates (X_A, Y_A). Takahashi can watch all fireworks whose launch points have a Euclidean distance of R or less from the point where he is standing.

Find the total satisfaction of the fireworks that Takahashi can watch.

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^9 \leq X_A, Y_A \leq 10^9
• 0 \leq R \leq 10^9
• -10^9 \leq X_i, Y_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq P_i \leq 10^4 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

4 0 0 5
3 4 10
5 0 20
6 0 30
-1 -1 5

Sample Output 1

35

Sample Input 2

3 10 10 2
0 0 100
13 10 200
10 13 300

Sample Output 2

0

Sample Input 3

10 -2 3 10
-2 3 50
8 3 70
-12 3 80
-2 14 90
4 9 30
-9 -1 40
20 20 100
-5 -6 60
6 -3 25
-11 10 35

Sample Output 3

355

Sample Input 4

30 100000000 -100000000 500000000
100000000 -100000000 100
600000000 -100000000 200
-400000000 -100000000 300
100000000 400000000 400
100000000 -600000000 500
450000000 250000000 600
500000000 200000000 700
700000000 -100000000 800
100000000 500000000 900
-100000000 -300000000 1000
300000000 -500000000 1100
-200000000 200000000 1200
400000000 -400000000 1300
-300000000 100000000 1400
200000000 100000000 1500
-350000000 -250000000 1600
550000000 -250000000 1700
250000000 -550000000 1800
-100000000 -550000000 1900
-450000000 -100000000 2000
1000000000 1000000000 2100
-1000000000 -1000000000 2200
999999999 -999999999 2300
-999999999 999999999 2400
123456789 -123456789 2500
-123456789 123456789 2600
400000000 300000000 2700
-250000000 -450000000 2800
550000000 150000000 2900
-300000000 -400000000 3000

Sample Output 4

30900

Sample Input 5

1 1000000000 -1000000000 0
1000000000 -1000000000 10000

Sample Output 5

10000

Problem Statement

Takahashi will train at a gym. The gym has N types of training machines, and using the i-th machine once provides an exercise effect of A_i. This exercise effect is fixed for each machine, and the same value is added each time the same machine is used.

Takahashi plans to use machines exactly K times. Each time, he chooses one of the N types of machines to use, but he cannot choose the same machine that was used immediately before. As long as this condition is satisfied, he is free to choose a machine that has been used in the past. Also, he may start with any machine on the first use.

Find the maximum total exercise effect that Takahashi can obtain from K training sessions.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq K \leq 10^9
• 1 \leq A_i \leq 10^9
• All inputs are integers

Sample Input 1

3 4
5 3 2

Sample Output 1

16

Sample Input 2

4 7
10 8 6 4

Sample Output 2

64

Sample Input 3

5 1000000000
1000000000 999999999 500000000 100 1

Sample Output 3

999999999500000000

Problem Statement

Takahashi is in charge of the lighting management system for a large building. The building has N rooms, and each room is assigned a number from 1 to N.

The lighting in each room has two states: "off" and "on". Initially, the lights in all rooms are off.

Takahashi performs Q operations. In the i-th operation (1 \leq i \leq Q), he toggles the lighting state of all rooms whose room numbers are between L_i and R_i, inclusive. That is, if a light is off, it is switched on, and if it is on, it is switched off.

The building has M "meeting rooms," and their room numbers are given as B_1, B_2, \ldots, B_M (not necessarily in ascending order).

After all Q operations have been completed, find the number of rooms among the M designated meeting rooms whose lights are on.

Constraints

• 1 \leq N \leq 10^9
• 1 \leq M \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq B_i \leq N (1 \leq i \leq M)
• All B_i are distinct
• 1 \leq L_i \leq R_i \leq N (1 \leq i \leq Q)
• All input values are integers

Sample Input 1

10 3 2
2 5 8
1 6
4 9

Sample Output 1

2

Sample Input 2

20 5 4
3 7 12 15 18
1 10
5 15
8 12
3 7

Sample Output 2

2

Sample Input 3

1000000000 10 8
1 100 999999999 500000000 250000000 750000000 123456789 987654321 42 1000000000
1 500000000
250000000 750000000
100 123456789
42 42
500000000 1000000000
1 100
987654321 999999999
42 100

Sample Output 3

2

Problem Statement

Takahashi works as a delivery person in a city. The city has N locations, each numbered from 1 to N.

The city has M roads, each connecting two locations bidirectionally. The i-th road (1 \leq i \leq M) connects location A_i and location B_i, and it takes C_i minutes to travel along this road. There may be multiple roads connecting the same pair of locations.

Takahashi starts from location 1, where the delivery center is, and delivers a package to location N by traveling along roads. A path from location 1 to location N is a sequence of locations v_0 = 1, v_1, v_2, \ldots, v_k = N (k \geq 1) such that for each j (0 \leq j \leq k-1), there exists at least one road connecting location v_{j} and location v_{j+1}. The same location may be visited multiple times.

The travel time of a path is determined as follows. For each j (0 \leq j \leq k-1), one road is chosen from among the roads connecting location v_j and location v_{j+1}, and the total of the travel times of the chosen roads is the travel time of the path.

If a path from location 1 to location N exists, output the minimum travel time (in minutes). If no path exists, output -1.

Constraints

• 2 \leq N \leq 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq A_i \leq N
• 1 \leq B_i \leq N
• A_i \neq B_i (no self-loops)
• 1 \leq C_i \leq 10^9
• All inputs are integers

Sample Input 1

4 4
1 2 3
2 4 5
1 3 2
3 4 7

Sample Output 1

8

Sample Input 2

3 1
1 2 10

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

20

Problem Statement

Takahashi and Aoki each have a dance choreography consisting of left and right steps. Takahashi's choreography is represented by string s, and Aoki's choreography is represented by string t, where each character is 0 (left step) or 1 (right step). Neither choreography contains three consecutive occurrences of the same step.

During rehearsal before the performance, Takahashi can perform the following modification at most K times:

• Choose one position in s or t, and change that step to the opposite step.
• However, after the change, the step at that position must differ from all adjacent steps within the same choreography.

After rehearsal, Takahashi pairs up some steps from s and t to create "synchro points." The pairing must satisfy all of the following conditions:

• Each pair consists of a position i in s and a position j in t.
• Only positions where s_i = t_j can be paired.
• Each position in s and each position in t can be used in at most one pair.
• Pairs must not cross each other. That is, for pairs (i, j) and (i', j'), if i < i' then j < j' must hold.

Determine the maximum number of pairs that can be made by performing modifications and pairing optimally.

Constraints

• 1 \leq |s| \leq 2 \times 10^5
• 1 \leq |t| \leq 2 \times 10^5
• |s| \times |t| \leq 2 \times 10^6
• s is a string consisting only of 0 and 1.
• t is a string consisting only of 0 and 1.
• s does not contain three or more consecutive occurrences of the same character.
• t does not contain three or more consecutive occurrences of the same character.
• 0 \leq K \leq |s| + |t|
• K is an integer.

Sample Input 1

0101
0011
1

Sample Output 1

3

Sample Input 2

01
10
0

Sample Output 2

1

Sample Input 3

010110100110110010101101001011
1010010110100110101100101101
5

Sample Output 3

24

Sample Input 4

001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011
110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100
40

Sample Output 4

100

Sample Input 5

0
1
2

Sample Output 5

1