Takım Çalışması#10401
Çiftçi John en sevdiği tatil için arkadaşlarına hediyeler göndermek istiyor. Hediye paketleme konusunda pek iyi olmadığından, ineklerinin yardımına başvurmak istiyor. Tahmin edebileceğiniz gibi, inekler de hediye paketleme konusunda kendilerinden pek iyi değiller — Çiftçi John'un zor yoldan öğreneceği bir ders.
Çiftçi John'un ineği bir sırada duruyor ve sırasıyla 'den 'ye kadar numaralandırılmışlar. İnek 'nin hediye paketleme beceri seviyesi s_i'dir. Bu beceri seviyeleri oldukça değişken olabileceğinden, FJ ineklerini takımlara bölmeye karar verir. Bir takım, en fazla ardışık inekten oluşan herhangi bir grup olabilir ve hiçbir inek birden fazla takıma ait olamaz. İnekler birbirlerinden öğrendiğinden, bir takımdaki her ineğin beceri seviyesi, o takımdaki en yetenekli ineğin beceri seviyesine yükseltilebilir.
FJ'ye takımları optimal şekilde oluşturarak elde edebileceği maksimum beceri seviyeleri toplamını belirlemesinde yardımcı olun.
İlk satır iki tam sayı içerir: ve k~(1 \le n \le 10^4, 1 \le k \le 10^3). Sonraki satırın her biri, ineklerin durduğu sıraya göre bir ineğin beceri seviyesini içerir. Her beceri seviyesi 10^5'i geçmeyen pozitif bir tam sayıdır.
Çiftçi John'un inekleri ardışık ineklerden oluşan takımlara bölerek elde edebileceği maksimum beceri seviyeleri toplamını temsil eden tek bir tam sayı yazdırın.
Bu örnekte, optimal çözüm ilk ineği ve son ineği gruplamaktır, ortadaki inek ise kendi başına bir takımda bırakılır (daha az sayıda, yani 'den az inekten oluşan takımlara da izin verildiğini hatırlayın). Sonuç olarak, ineğin beceri seviyeleri , , , , , , olur ve bunların toplamı 'tür.
Örnek 1