// Arup Guha
// 10/3/2023

// Alternate Solution to Fall 2023 COP 3502 RP3: Dirty Driving (via Quick Sort)
/*** Edited on 11/11/2023 to verify solution for COP 3502 Exam 2 alternate partition
     and Insertion Sort for Thursday Exam 2
***/

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

void quicksort(int* arr, int low, int high);
int partition(int* arr, int low, int high);
void swap(int* arr, int i, int j);
void insertionsort(int* array, int low, int high);

int main() {

    srand(time(0));

    int n, mult;
    scanf("%d%d", &n, &mult);

    // Allocate memory, read in values.
    int* dist = calloc(n, sizeof(int));
    for (int i=0; i<n; i++)
        scanf("%d", &(dist[i]));

    // Sort values.
    quicksort(dist, 0, n-1);

    // Safe initial value.
    int res = 1;

    // Look at each car in order.
    for (int i=0; i<n; i++) {

        // Here is where we need to be for this car.
        int cur = mult*(i+1) - dist[i] + dist[0];

        // Update if necessary.
        if (cur > res) res = cur;
    }

    // Ta da!
    printf("%d\n", res);
    free(dist);
    return 0;
}

// Quick sorts arr[low..high].
void quicksort(int* arr, int low, int high) {

    /*** edit to test insertion sort solution ***/
    if (high - low < 40) {
        insertionsort(arr, low, high);
        return;
    }

    int mid = partition(arr, low, high);
    quicksort(arr, low, mid-1);
    quicksort(arr, mid+1, high);
}

/*** Exam 2A Question Code ***/
int partition(int* array, int low, int high) {

    /*** Added this to avoid TLE ***/
    int tmpPos = rand()%(high-low+1) + low;
    swap(array, tmpPos, low);

    // Allocate memory for copied values.
    int* tmp = calloc(high-low+1, sizeof(int));
    int lowPtr = 0, highPtr = high-low;

    // Compare all of these to the partition element array[low].
    for (int i=low+1; i<=high; i++) {

        // Go on left.
        if (array[ i ] < array[ low ])
            tmp[lowPtr++] = array[i];

        // Go on right.
        else
            tmp[highPtr--] = array[i];
    }

    // Put the partition element in place.
    tmp[ lowPtr ] = array[ low ]; // LHS index could be lowPtr or highPtr

    // Copy back, pay attention to indexing.
    for (int i=low; i<=high; i++)
        array[i] = tmp[i-low];
    free(tmp);

    // This is tricky...low is our offset, lowPtr was index into tmp...
    return low+lowPtr ; // Could be lowPtr or highPtr
}


// Swaps arr[i] and arr[j].
void swap(int* arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

// Answer for Exam 2 Thursday Question 2
void insertionsort(int* array, int low, int high) {

    // Insert the item at index i.
    for (int i=low+1; i<=high; i++) {

        int tmpIdx = i;

        // Swap until we find the right place for the element.
        while (tmpIdx > low && array[tmpIdx] < array[tmpIdx-1]) {

            // Swap successive elements.
            int tmp = array[tmpIdx];
            array[tmpIdx] = array[tmpIdx-1];
            array[tmpIdx-1] = tmp;

            // Update down.
            tmpIdx--;
        }
    }
}