Sweet Lovin’ Sampriti

0

0 votes
Ad-Hoc, Easy-Medium
Problem

Sampriti is a self-confessed sweet lover. Please find proof enclosed below:

This is Sampriti's actual DP on WhatsApp. You are free to check if you have her contact number

  • She loves them so much that she buys and stock them in boxes to munch on for N days..
  • On the ith day she eats Ti number of sweets. To stock the sweets she numbers each sweet starting at 1 to Ti for each day (so that no one can steal them).
  • She stores them in box that can hold upto K sweets. If more than K sweets are present in a day, she uses multiple boxes.
  • Each new day she starts with a new box. She also indexes the boxes starting from 1.

Sampriti believes a sweet to be Yummylicious if its index (for a day) is same as the box number it is stored in. Given the schedule for her sweets feast can you count the number of Yummylicious sweets she’s gonna have?
Note: See the diagram in the Explanation section for more details.

Input Format
The first line contains two integers N and K — the number of days and the maximum number of sweets per box respectively.
The second line contains N integers T1, T2,…,Tn where Ti denotes the number of sweets Sampriti eats on the ith day.

Output Format
Print the number of Yummylicious sweets Sampriti has.

Constraints
1≤ N, K, Ti ≤100

Sample Input
5 3
4 2 6 1 9
Sample Output
3
Time Limit: 0.3
Memory Limit: 256
Source Limit:
Explanation

The diagram below depicts Sampriti’s sweet feast with N=5 days and a maximum of K=3 sweets per box. Yummylicious sweets are outlined in red, and box numbers numbers are in squares.

There are 3 Yummylicious sweets and thus we print the number 3 on a new line.

Contributers:
Editor Image

?