AIOC Banner

Problem: Guards

Want to try solving this problem? You can submit your code online if you log in or register.


Guards

Time Limit: 1.5 seconds
Memory Limit: 30 Mb

The time has come for the annual Boomerang and Bagel Throwing Olympiad, and the hosts have spared no expense. A large portion of the city has been sealed off completely to house the athletes and journalists, not to mention the barbeque makers and French pastry chefs. Amidst the hype and excitement, you have found yourself in charge of the security of this event.

Every road coming into the Olympiad grounds has been blocked off, to ensure that there are no unwanted intruders. However, the hosts have spent so much money on the opening and closing ceremonies that there is not enough money left to hire enough security guards. Your aim is to hire as few guards as possible but still keep the grounds secure.

The Olympiad grounds can be thought of as a large circular region, with roads coming in at various points on the border. The government requires that every point where a road enters the grounds must be at most k metres from a security guard, where distance is measured around the edge of the circle. Guards may only be placed at roads; they may not be placed in the regions in between.

An example is shown in the diagram below. Here there are seven roads coming into the grounds, with the distances between them marked on the diagram. Suppose that the government has declared that k = 30. In this case, by placing three guards at the roads marked with stars, you can ensure that every road is watched.

Your task is, given the distances between roads and the value of k, to determine the smallest number of guards that are required.

Constraints

Furthermore, for 30% of the available marks, the number of roads will satisfy 1 <= n <= 1,000.

Input

Your program must read from standard input. The first line will contain the integers n and k separated by a single space, as described above.

Following this will be n lines, each describing the distance between two adjacent roads. These distances will be given in order as one travels around the circle.

More precisely, suppose that the roads are numbered 1,2,...,n in clockwise order around the circle. Then the ith of these lines will be the clockwise distance between the ith and (i+1)th roads, with the nth line giving the clockwise distance between the nth and first roads.

Output

Your program must write a single line to standard output. This line must contain a single integer giving the smallest number of security guards required.

Sample Input

7 30
30
40
10
40
50
20
10

Sample Output

3

Scoring

The score for each input scenario will be 100% if the correct answer is output, or 0% otherwise.

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 24 May 2019, 11:21pm AEST