Tổng cộng có \(12\) cô bò của Farmer John tham dự Thế vận hội Moolympic mùa đông năm nay, mỗi cô có một mức kỹ năng nguyên từ \(1\) đến \(1\,000\,000\).

Farmer John muốn chia họ thành \(4\) đội, mỗi đội \(3\) cô bò, sao cho các đội tương đối "cân bằng" về tổng kỹ năng; mức kỹ năng của một đội chính là tổng mức kỹ năng của các cô bò trong đội. Cụ thể, ông muốn tối thiểu hóa \(S-s\), trong đó \(S\) và \(s\) lần lượt là mức kỹ năng lớn nhất và nhỏ nhất trong số các đội. Nhờ vậy, chênh lệch giữa đội giỏi nhất và đội kém nhất sẽ nhỏ nhất có thể.

Hãy giúp Farmer John xác định giá trị nhỏ nhất có thể của \(S-s\).

Dữ liệu vào

Gồm \(12\) dòng, mỗi dòng chứa mức kỹ năng của một cô bò.

Ràng buộc

• Có đúng \(12\) cô bò.
• Mức kỹ năng của mỗi cô bò là một số nguyên trong đoạn từ \(1\) đến \(1\,000\,000\).

Dữ liệu ra

In ra giá trị nhỏ nhất có thể của \(S-s\).

Ví dụ

1
2
3
4
5
6
7
8
9
10
11
12

1

Nguồn

USACO 2014 January Contest, Bronze — Problem 3: Balanced Teams

Tác giả: Brian Dean, 2014.