Houses and Schools

There are n houses on a street, numbered 1,2,\dots,n. The distance of houses a and b is |a-b|. You know the number of children in each house. Your task is to establish k schools in such a way that each school is in some house. Then, each child goes to the nearest school. What is the minimum total walking distance of the children if you act optimally? Input The first input line has two integers