Bài tập môn Độc dược

Có $n$ học sinh, mỗi học sinh được giao đúng một nhiệm vụ. Học sinh thứ $i$ có độ lười $a_i$, đồng thời nhiệm vụ ban đầu của học sinh đó có độ khó cũng bằng $a_i$.

Các học sinh muốn phân phối lại nhiệm vụ sao cho mỗi học sinh vẫn làm đúng một nhiệm vụ và mỗi nhiệm vụ được giao cho đúng một học sinh (tức là ta gán các nhiệm vụ cho học sinh theo một hoán vị bất kỳ). Thời gian một học sinh hoàn thành một nhiệm vụ bằng tích của độ lười của học sinh đó với độ khó của nhiệm vụ được giao.

Hãy tìm tổng thời gian nhỏ nhất để hoàn thành tất cả các nhiệm vụ khi phân phối một cách tối ưu. In kết quả theo modulo $10007$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số học sinh (cũng là số nhiệm vụ).
• $n$ dòng tiếp theo, mỗi dòng chứa một số nguyên $a_i$ là độ lười của học sinh thứ $i$ (cũng là độ khó của nhiệm vụ ban đầu của học sinh đó).

Dữ liệu ra

• Một số nguyên duy nhất: tổng thời gian nhỏ nhất để hoàn thành tất cả nhiệm vụ, lấy theo modulo $10007$.

Ràng buộc

• $1\le n\le 100000$
• $1\le a_i\le 100000$

Ví dụ