Baštovan Toma je rešio da ulepša svoje prostrano dvorište tako što će ga ukrasiti cvećem. On naime želi da najpre postavi n saksija u red (1 ≤ n ≤ 1000000) i da u svakoj od ovih n saksija bude k kilograma zemlje (0 ≤ k ≤ 1000), a da potom u njima sadi raznorazno cveće. On je zato od firme koja se bavi prodajom saksija naručio n saksija takvih da se u svakoj od tih n saksija nalazi k kilograma zemlje. Ta firma je bila toliko ljubazna da mu ne samo donese te saksije već i da ih postavi u red. Međutim, sutradan je Toma doživeo veliki šok. Neke saksije imaju više, a neke manje od k kilograma zemlje. Toma se ipak malo smirio kada je primetio da je ukupna težina zemlje u svim saksijama k · n kilograma - pa se ipak ova greška da ispraviti. Toma želi da prebacivanjem zemlje iz jedne u drugu saksiju učini da u svakoj saksiji bude k kilograma zemlje, a da se pri tome najmanje umori. Toma zna da za prebacivanje x kilograma zemlje iz saksije koja je i-ta po redu u saksiju koja je j-ta po redu utroši x · |i - j| džula energije. Odrediti koliko je minimalno energije koju Toma mora potrošiti da bi ispravio grešku firme koja mu je prodala saksije.

Ulaz:

(Ulazni podaci se nalaze u datoteci saksije.in) U prvom redu tekstualne datoteke nalaze se redom celi brojevi n i k. U drugom redu ove datoteke nalazi se n celih brojeva koji su veći ili jednaki 0. Naime i-ti broj (1 ≤ i ≤ n) u drugom redu označava koliko se kilograma zemlje nalazi u i-toj saksije kada se gleda sa prozora Tomine spavaće sobe sa leva na desno.

Izlaz:

(Izlazne podatke upisati u datoteku saksije.out) U izlaznu datoteku treba upisati jedan broj koji je jednak W mod 1000000000, gde je W jednak minimalnom broju Džula koje Toma mora potrošiti da bi ispravio grešku firme od koje je kupio saksije.

Primer:

6 4
5 6 2 1 7 3

8

#include <stdio.h>
#include <stdlib.h>

void main()
{
  FILE *dat;
  dat=fopen("Saksije.in","r");
  int n,k;
  fscanf(dat,"%d%d",&n,&k);
  int *A,i;
  A=(int *)malloc(n*sizeof(int));
  for (i=0;i<n;i++)
    fscanf(dat,"%d",A+i);
  fclose(dat);

  int suma=0;
  for (i=0;i<n-1;i++)
  {
    if (A[i]>k)
    {
      suma=(suma+A[i]-k)%1000000000;
      A[i+1]+=A[i]-k;
    }
    else
    {
      suma=(suma+k-A[i])%1000000000;
      A[i+1]-=k-A[i];
    }
  }
  
  dat=fopen("Saksije.out","w");
  fprintf(dat,"%d\n",suma);
  fclose(dat);
}