Chia nhóm tối ưu (Optimal Grouping)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ học sinh, học sinh thứ $i$ có điểm năng lực $X_i$. Cần chia toàn bộ học sinh thành các nhóm; mỗi học sinh thuộc đúng một nhóm.

Số học sinh trong mỗi nhóm phải nằm trong đoạn $[L,R]$. Chi phí của một nhóm bằng hiệu giữa điểm năng lực lớn nhất và nhỏ nhất trong nhóm.

Hãy tìm tổng chi phí nhỏ nhất của một cách chia hợp lệ. Nếu không thể chia, in -1.

Input

• Dòng đầu chứa ba số nguyên $N,L,R$.
• Dòng thứ hai chứa $N$ số nguyên $X_1,X_2,\ldots,X_N$.

Output

In một số nguyên duy nhất là tổng chi phí nhỏ nhất, hoặc -1 nếu không tồn tại cách chia hợp lệ.

Subtask

• Subtask 1 — 25%: $1\le L\le R\le N\le 20$, $0\le X_i\le 10^9$.
• Subtask 2 — 25%: $1\le L\le R\le N\le 2000$, $0\le X_i\le 10^9$.
• Subtask 3 — 20%: $1\le L=R\le N\le 2\cdot 10^5$, $0\le X_i\le 10^9$.
• Subtask 4 — 30%: $1\le L\le R\le N\le 2\cdot 10^5$, $0\le X_i\le 10^9$.

Ví dụ

Ví dụ 1

Input

5 2 3
12 2 10 1 11

Output

3

Giải thích

Sắp xếp thành $1,2,10,11,12$. Chia $\{1,2\}$ và $\{10,11,12\}$, tổng chi phí là $1+2=3$.

Ví dụ 2

Input

5 3 3
1 2 3 4 5

Output

-1

Giải thích

Mỗi nhóm phải có đúng $3$ học sinh nên không thể chia hết $5$ học sinh.