BPC 1 S3 - Bus Stops

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

There is a large, circular, one-way road, driven on by a number of evenly spaced buses, with an equal number of evenly spaced bus stations placed next to it. Each bus and station belongs to one of N colours. There are a_i buses and a_i stations of the i^{\text{th}} colour (1 \le i \le N). Over a period of time, buses will drive clockwise, remaining spaced equally, each passing exactly X stations, and then stop moving. You are allowed to permute all of the buses and stations however you want before the buses start driving. When a bus passes a station of the same colour, the bus will visit it. You must find the maximum number of visits that can occur.

Note that a bus can visit the same station multiple times.


1 \le N \le 2 \times 10^5

1 \le a_i \le 10^6

0 \le X \le 2 \times 10^{11}

Subtask 1 [10%]

\sum_{i=1}^{i=N} a_i \le 5 \times 10^3

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line contains two integers, N and X.

The second line contains N integers, a_i.

Output Specification

Output a single line containing an integer, the maximum number of times buses will visit a station.

Sample Input

2 3
2 2

Sample Output


Explanation for Sample

We can place buses and stops like this (the first row is the stops, and the second row is the buses):

2 2 1 1
1 1 2 2

Since X=3, we will need to consider 3 positions:

At time 0, there are 2 visits:

2 2 1 1
2 1 1 2

At time 1, there are 4 visits:

2 2 1 1
2 2 1 1

At time 2, there are 2 visits:

2 2 1 1
1 2 2 1


There are no comments at the moment.