距離と襲われる確率をまとめてオブジェクトにして、確率の大きい順にソート。
あとは区間の一部でも護衛を雇えることに気をつけながら、
確率の高い区間から順に料金を支払っていけばいい。
for (int i = 0; i < N; i++) {
Root root = array[i];
if (M > 0) {
while (root.distance > 0 && M > 0) {
root.distance--;
M--;
}
}
ans += root.distance * root.probable;
}