Vanya smashes potato in a vertical food processor. At each moment of time the height of the potato in the processor doesn't exceed h and the processor smashes k centimeters of potato each second. If there are less than k centimeters remaining, than during this second processor smashes all the remaining potato.

Vanya has n pieces of potato, the height of the i-th piece is equal to ai. He puts them in the food processor one by one starting from the piece number 1 and finishing with piece number n. Formally, each second the following happens:

  1. If there is at least one piece of potato remaining, Vanya puts them in the processor one by one, until there is not enough space for the next piece. 
  2. Processor smashes k centimeters of potato (or just everything that is inside). 



Provided the information about the parameter of the food processor and the size of each potato in a row, compute how long will it take for all the potato to become smashed.

Input

The first line of the input contains integers n, h and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ h ≤ 109) — the number of pieces of potato, the height of the food processor and the amount of potato being smashed each second, respectively.

The second line contains n integers ai (1 ≤ ai ≤ h) — the heights of the pieces.

Output

Print a single integer — the number of seconds required to smash all the potatoes following the process described in the problem statement.

Examples

Input

5 6 3
5 4 3 2 1


Output

5


Input

5 6 3
5 5 5 5 5


Output

10


Input

5 6 3
1 2 1 1 1


Output

2

Note

Consider the first sample. 

  1. First Vanya puts the piece of potato of height 5 into processor. At the end of the second there is only amount of height 2 remaining inside. 
  2. Now Vanya puts the piece of potato of height 4. At the end of the second there is amount of height 3 remaining. 
  3. Vanya puts the piece of height 3 inside and again there are only 3 centimeters remaining at the end of this second. 
  4. Vanya finally puts the pieces of height 2 and 1 inside. At the end of the second the height of potato in the processor is equal to 3. 
  5. During this second processor finally smashes all the remaining potato and the process finishes. 



In the second sample, Vanya puts the piece of height 5 inside and waits for 2 seconds while it is completely smashed. Then he repeats the same process for 4 other pieces. The total time is equal to 2·5 = 10 seconds.

In the third sample, Vanya simply puts all the potato inside the processor and waits 2 seconds.
#include <bits/stdc++.h>
using namespace std;
inline namespace Infinity {
inline namespace IO {
const char CR = '\n';
const char SP = ' ';
inline void write(const int n) { printf("%d", n); }
inline void write(const unsigned n) { printf("%u", n); }
inline void write(const long long n) { cout << n; }
inline void write(const unsigned long long n) { cout << n; }
inline void writef(const double a, const int n = 15) { printf("%.*f", n, a); }
inline void writef(const long double a, const int n = 18) {
  cout << setprecision(n) << fixed << a;
}
inline void write(const char c) { printf("%c", c); }
inline void write(const char s[]) { printf("%s", s); }
inline void write(const string &s) { printf("%s", s.data()); }
inline void write(const pair<int, int> &p) {
  printf("%d %d", p.first, p.second);
}
template <class T>
inline void write(const T a) {
  for (auto i = a.begin(); i != a.end(); i++) {
    if (i != a.begin()) write(SP);
    write(*i);
  }
}
inline void writeln() { write(CR); }
template <typename T>
inline void writeln(const T &a) {
  write(a);
  write(CR);
}
inline void writefln(const double a, int n) {
  printf("%.*f", n, a);
  write(CR);
}
inline void writefln(const long double a, int n = 18) {
  cout << setprecision(n) << fixed << a << endl;
}
inline void writesln(const int *a, const int l, const int r) {
  for (int i = l; i <= r; i++) printf("%d ", a[i]);
  writeln(CR);
}
template <class T>
inline void writelns(const T &a) {
  for (auto n : a) writeln(n);
}
template <typename T, typename... types>
inline void write(const T &a, const types &...args) {
  write(a);
  write(args...);
}
template <typename... types>
inline void writeln(const types &...args) {
  write(args...);
  write(CR);
}
template <typename... types>
inline void writeSP(const types &...args) {
  write(args...);
  write(SP);
}
inline void writelnYN(bool b) { writeln(b ? "YES" : "NO"); }
inline void writelnyn(bool b) { writeln(b ? "Yes" : "No"); }
string caseSharpSpace(int n) { return "Case #" + to_string(n) + ": "; }
string caseNoSharpSpace(int n) { return "Case " + to_string(n) + ": "; }
string caseSharpNoSpace(int n) { return "Case #" + to_string(n) + ":"; }
string caseNoSharpNoSpace(int n) { return "Case " + to_string(n) + ":"; }
inline int read(int &n) { return scanf("%d", &n); }
inline int read(long long &n) { return cin >> n ? 1 : -1; }
template <typename T, typename... types>
inline int read(T &n, types &...args) {
  read(n);
  return read(args...);
}
inline char getcc() {
  char c;
  do c = getchar();
  while (c == ' ' || c == '\n');
  return c;
}
inline int getint() {
  int n;
  read(n);
  return n;
}
inline long long getll() {
  long long n;
  read(n);
  return n;
}
inline double getdouble() {
  double n;
  scanf("%lf", &n);
  return n;
}
inline vector<int> getints(int n) {
  vector<int> v(n);
  for (int i = 0; i < n; i++) v[i] = getint();
  return v;
}
inline vector<pair<int, int> > getpairs(int n) {
  vector<pair<int, int> > v(n);
  for (int i = 0; i < n; i++) {
    int a = getint(), b = getint();
    v[i] = pair<int, int>(a, b);
  }
  return v;
}
inline void read(string &str, const unsigned size) {
  char s[size];
  scanf("%s", s);
  str.assign(s);
}
inline string getstr(const unsigned size = 1048576) {
  string s;
  read(s, size + 1);
  return s;
}
inline string getln(const unsigned size = 1048576) {
  char s[size + 1];
  scanf("%[^\n]", s);
  getchar();
  return string(s);
}
}  // namespace IO
inline namespace Functions {
inline constexpr int ctoi(const char c) { return c - '0'; }
inline constexpr char itoc(const int n) { return n + '0'; }
inline int dtoi(const double d) { return round(d); }
template <typename T>
inline constexpr bool in(T x, T l, T r) {
  return l <= x && x <= r;
}
template <class T>
inline int size(const T &a) {
  return a.size();
}
template <typename T1, typename T2>
inline constexpr pair<T1, T2> mkp(const T1 &a, const T2 &b) {
  return make_pair(a, b);
}
template <class T>
inline void sort(T &a) {
  std::sort(a.begin(), a.end());
}
template <class T1, class T2>
inline void sort(T1 &a, T2 comp) {
  std::sort(a.begin(), a.end(), comp);
}
template <class T1, typename T2>
inline int lbound(const T1 &a, const T2 k) {
  return lower_bound(a.begin(), a.end(), k) - a.begin();
}
template <class T1, typename T2>
inline int ubound(const T1 &a, const T2 k) {
  return upper_bound(a.begin(), a.end(), k) - a.begin();
}
template <class T1, class T2>
int count(T1 &a, T2 k) {
  return ubound(a, k) - lbound(a, k);
}
template <class T1, class T2>
int find(T1 &a, T2 k) {
  return count(a, k) ? lbound(a, k) : -1;
}
template <typename T>
inline void clear(T &a) {
  memset(a, 0, sizeof a);
}
template <typename T>
T gcd(T a, T b) {
  while (b) {
    T t = a % b;
    a = b;
    b = t;
  }
  return a;
}
template <typename T>
T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
long long qpow(long long a, long long b, long long c) {
  return b ? qpow(a * a % c, b >> 1, c) * (b & 1 ? a : 1) % c : 1;
}
template <typename T>
T exGcd(T a, T b, T &x, T &y) {
  T d = a;
  if (b) {
    d = exGcd(b, a % b, y, x);
    y -= a / b * x;
  } else {
    x = 1;
    y = 0;
  }
  return d;
}
template <typename T>
T constexpr mps(T l, T r, T k) {
  return ((r - (r % k + k) % k) - (l + (k - l % k) % k)) / k + 1;
}
template <typename T>
T constexpr sgn(T a) {
  return a == 0 ? 0 : a > 0 ? 1 : -1;
}
template <typename T>
constexpr T sq(T a) {
  return a * a;
}
template <typename T>
constexpr bool odd(T a) {
  return bool(a % 2);
}
template <typename T>
constexpr bool even(T a) {
  return !bool(a % 2);
}
template <typename T1, typename T2>
constexpr T1 smod(T1 x, T2 m) {
  return x > m ? x - m : x + m > m ? x : x + m;
}
template <typename T, typename F>
T dichotomy(T l, T r, F check, T diff = 1) {
  while (r - l > diff) {
    T m = l + (r - l) / 2;
    check(m) ? l = m : r = m;
  }
  return l;
}
}  // namespace Functions
inline namespace TypeDefine {
using uint = unsigned int;
using ull = unsigned long long int;
using ld = long double;
}  // namespace TypeDefine
inline namespace Constant {
const int maxint = INT_MAX;
const long long maxll = LLONG_MAX;
constexpr const array<int, 10> pow10({1, 10, 100, 1000, 10000, 100000, 1000000,
                                      10000000, 100000000, 1000000000});
}  // namespace Constant
}  // namespace Infinity
int main(int argc, char *argv[]) {
  int n = getint(), h = getint(), k = getint();
  vector<int> a = getints(n);
  long long t = 0, s = 0;
  int i = 0;
  while (i < n) {
    while (i < n && s + a[i] <= h) s += a[i++];
    t += s / k;
    s %= k;
    if (i < n && s + a[i] > h) {
      t++;
      s = 0;
    }
  }
  t += s / k;
  s %= k;
  if (s) t++;
  writeln(t);
  return 0;
}
