## BPC 1 S3 - Bus Stops

View as PDF

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

Authors:
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 colours. There are buses and stations of the colour (). Over a period of time, buses will drive clockwise, remaining spaced equally, each passing exactly 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.

#### Input Specification

The first line contains two integers, and .

The second line contains integers, .

#### Output Specification

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

2 3
2 2

8

#### 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 , we will need to consider positions:

At time , there are visits:

2 2 1 1
2 1 1 2

At time , there are visits:

2 2 1 1
2 2 1 1

At time , there are visits:

2 2 1 1
1 2 2 1