Problem Statement

Takahashi is visiting a shop specializing in cabbage.

The shop sells cabbage for X yen (Japanese currency) per head.
However, if you buy more than A heads of cabbage at once, the (A+1)-th and subsequent heads will be sold for Y yen per head.
(It is guaranteed that Y \lt X. See Sample Input/Output 1 for clarity.)

Print the amount of money needed to buy N heads of cabbage.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A \leq 10^5
• 1 \leq Y \lt X \leq 100
• All values in input are integers.

Sample Input 1

5 3 20 15

Sample Output 1

90

You need to pay 20 yen for each of the 1-st through 3-rd heads of cabbage, and 15 yen for each of the 4-th and 5-th heads of cabbage.
Thus, you need to pay a total of 20+20+20+15+15 = 90 yen for the 5 heads of cabbage.

Sample Input 2

10 10 100 1

Sample Output 2

1000

Problem Statement

We have a deck of N cards.
Each of these cards is good or bad.

Using this deck, Takahashi and Aoki will play a game against each other.
In the game, the players alternately draw the topmost card and eat it.
The player who first gets to eat a bad card loses the game. (Here, it is guaranteed that the deck contains at least one bad card.)

You are given a string S consisting of 0 and 1. For each i = 1, 2, \ldots, N,

• if the i-th character of S is 0, it means that the i-th card from the top of the deck is good;
• if the i-th character of S is 1, it means that the i-th card from the top of the deck is bad.

Which player will lose when Takahashi goes first in the game?

Constraints

• 1 \leq N \leq 10^5
• N is an integer.
• S is a string of length N consisting of 0 and 1.
• S contains at least one occurrence of 1.

Sample Input 1

5
00101

Sample Output 1

Takahashi

First, Takahashi will eat a good card. Next, Aoki will eat a good card. Then, Takahashi will eat a bad card.
Thus, Takahashi will be the first to eat a bad card, so we should print Takahashi.

Sample Input 2

3
010

Sample Output 2

Aoki

Problem Statement

There are N candies arranged in a row from left to right.
Each of these candies has one color that is one of the 10^9 colors called Color 1, Color 2, \ldots, and Color 10^9.
For each i = 1, 2, \ldots, N, the color of the i-th candy from the left is Color c_i.

From this row, Takahashi can choose K consecutive candies and get them.
That is, he can choose an integer i such that 1 \leq i \leq N-K+1 and get the i-th, (i+1)-th, (i+2)-th, \ldots, (i+K-1)-th candy from the left.

Takahashi likes to eat colorful candies, so the more variety of colors his candies have, the happier he will be.
Print the maximum possible number of distinct colors in candies he gets.

Constraints

• 1 \leq K \leq N \leq 3 \times 10^5
• 1 \leq c_i \leq 10^9
• All values in input are integers.

Sample Input 1

7 3
1 2 1 2 3 3 1

Sample Output 1

3

If Takahashi gets the 3-rd through 5-th candies, they will have 3 distinct colors, which is the maximum possible number.

Sample Input 2

5 5
4 4 4 4 4

Sample Output 2

1

Takahashi can get all of these candies, but they are in a single color.

Sample Input 3

10 6
304621362 506696497 304621362 506696497 834022578 304621362 414720753 304621362 304621362 414720753

Sample Output 3

4

Problem Statement

The Kingdom of Takahashi can be represented as a grid with H rows and W columns. Let (i, j) denote the square at the i-th row from the north and j-th column from the west.

Recently, there have been more and more requests from the kingdom's citizens to build a railway, and now the king, Takahashi, has no choice but to build one.
The construction of the railway will have the following two phases.

• First, choose two different squares and build a station on each of them. It costs A_{i,j} yen to build a station on the square (i, j).
• Then, build a railway track connecting these two stations. This costs C \times (|i-i'| + |j-j'|) yen when the two stations are on the squares (i, j) and (i', j'). (|x| denotes the absolute value of x.)

Takahashi's priority is to spend as little as possible on this construction, rather than to improve convenience for the citizens.
Print the minimum possible total cost of the construction of the railway.

Constraints

• 2 \leq H, W \leq 1000
• 1 \leq C \leq 10^9
• 1 \leq A_{ij} \leq 10^9
• All values in input are integers.

Sample Input 1

3 4 2
1 7 7 9
9 6 3 7
7 8 6 4

Sample Output 1

10

If we build stations on the squares (1, 1) and (2, 3), it will cost 1 + 3 = 4 yen to build the stations and 2 \times (|1-2| + |1-3|) = 6 yen to build the track, for a total of 4+6 = 10 yen. This is the minimum possible total cost of the construction.

Sample Input 2

3 3 1000000000
1000000 1000000 1
1000000 1000000 1000000
1 1000000 1000000

Sample Output 2

1001000001

Problem Statement

We have an undirected graph with N vertices and 0 edges. Let us call the N vertices Vertex 0, Vertex 1, Vertex 2, \ldots, Vertex N-1.

Consider M kinds of operations on this graph.
For each i = 1, 2, \ldots, M, the operation of the i-th kind is to choose an integer x such that 0 \leq x \lt N and add an undirected edge connecting Vertex x and Vertex (x + A_i) \bmod N. Here, a \bmod b denotes the remainder when dividing a by b. It costs C_i yen to do the operation of the i-th kind once.

You can do these M kinds of operations any number of times (possibly zero) in any order. For example, if three kinds of operations are available, you can choose to do the first operation twice, the second zero times, and the third once.

Determine whether it is possible to make the graph connected. If it is possible, find the minimum total cost needed to do so.

Constraints

• 2 \leq N \leq 10^9
• 1 \leq M \leq 10^5
• 1 \leq A_i \leq N-1
• 1 \leq C_i \leq 10^9
• All values in input are integers.

Sample Input 1

4 2
2 3
3 5

Sample Output 1

11

If we first do the operation of the first kind to connect Vertices 0 and 2, then do it again to connect Vertices 1 and 3, and finally the operation of the second kind to connect Vertices 1 and 0, the graph will be connected. The total cost incurred here is 3+3+5 = 11 yen, which is the minimum possible.

Sample Input 2

6 1
3 4

Sample Output 2

-1

There is no way to make the graph connected, so we should print -1.

Problem Statement

We have N cards arranged in a row on a table. For each i = 1, 2, \ldots, N, the i-th card has an integer A_i written on the front and an integer B_i written on the back. Initially, every card is placed face up.

Takahashi will choose any number of cards he likes (possibly zero) and flip them. Then, he will be happy if the following condition is satisfied:

• for every pair of integers (i, j) such that 1 \leq i \lt j \leq N, the integers visible on the i-th and j-th cards are coprime.

Determine whether it is possible for Takahashi to be happy.

Constraints

• 1 \leq N \leq 3 \times 10^4
• 1 \leq A_i, B_i \leq 2 \times 10^6
• All values in input are integers.

Sample Input 1

3
2 5
10 9
4 8

Sample Output 1

Yes

Initially, we see integers 2, 10, and 4. If we flip the first and second cards, we will see 5, 9, and 4, which will make Takahashi happy. Thus, we should print Yes.

Sample Input 2

2
10 100
1000 10000

Sample Output 2

No

There is no way to flip cards to make Takahashi happy, so we should print No.