Minimum Difference in Book Piles

You are given n books, each with a specified thickness. Your task is to split these books into two piles such that the absolute difference between the total thickness of the two piles is minimized.

This problem is a variation of the classic Partition Problem. Let \(S\) be the total thickness of all books. You need to select a subset having sum \(T\) so that the value \(|S - 2T|\) is minimized. Use dynamic programming to determine the optimal partition.

inputFormat

The input is read from stdin and consists of two lines.

• The first line contains an integer \(n\) (1 \(\leq\) n \(\leq\) 1000), representing the number of books.
• The second line contains \(n\) space-separated integers, each representing the thickness of a book.

outputFormat

Output a single integer to stdout which is the minimum possible absolute difference between the total thicknesses of the two piles.

## sample

1
5

5

</p>