P5132 Cozy Glow Saves Equestria.

This problem is at Junior- difficulty. Players from both NOIP groups, please all get it accepted (~~otherwise you might not even keep your NOIP provincial third prize~~). PS: Three years of OI end up as nothing, and on Day 1 T1 you meet your ancestors...

Cozy Glow secretly built a magic array. This magic array is absorbing the magic of Equestria, so you must destroy it as soon as possible. This magic array consists of several artifacts. Each artifact has a magic power value, and every pair of artifacts also has an association value. You need to remove these artifacts one by one. However, every time you remove an artifact, you will suffer a certain amount of backlash. The amount of backlash equals the sum of the association values between this artifact and all other artifacts that are still present, multiplied by this artifact’s magic power value. In order to reduce the backlash, tb148 needs to take away every artifact. But because he is afraid of dying, he wants the total sum of backlash values to be as small as possible. Now tb148 wants to know: in what order should the artifacts be removed to make the total backlash minimum?

The first line contains the number of artifacts. The second line contains the magic power value of each artifact. Next, the association values between artifacts are given in the form of an adjacency matrix.

Output the total backlash value produced by the best removal order.

Constraints: Number of artifacts $\le 1000$. All other values $\le 2000000$. The numbers on the main diagonal are guaranteed to be $0$... Translated by ChatGPT 5