HUNTER×HUNTER#10896
Има некоја игра која се вика Hunter x Hunter. Нека секој од N-те натпреварувачи е означен со реден број од 0 до N - 1. На почетокот на едно ниво од играта, секој натпреварувач добива беџ на кој е запишан неговиот реден број. Исто така, на секое од N ливчиња е напишан еден од броевите од 0 до N - 1 при што нема две ливчиња со ист број. Ливчињата се ставени во сад. Натпреварувачот извлекува ливче (и не го враќа назад); бројот кој е напишан на ливчето, T_i, ја претставува „метата" на натпреварувачот. Откако сите ќе извлечат, секој има по една мета. Се знае дека никој не си го извлекол сопствениот број, т.е. T_i \neq i за секое .
Потоа, натпреварувачите ги оставаат на остров една седмица и тие може меѓусебно да си ги крадат беџовите. На крајот од седмицата, се запишува кој кои беџови ги има кај него. Поените на еден натпреварувач се пресметуваат така што ако натпреварувачот се уште го има неговиот беџ, ќе добие поени, а ќе добие уште поени ако го има и беџот на неговата мета T_i. За секој друг беџ кој го има ќе добие само по 1 поен. Само натпреварувачите кои имаат освоени барем поени преминуваат на следното ниво.
Очигледно, не може сите натпреварувачи да преминат на следно ниво. Вие ја следите играта онлајн и за секој натпреварувач кој ќе премине на следното ниво ќе добиете по L_i денари. Вас ве интересира колку најмногу пари може да добиете ако се случи најдобрата можна ситуација.
Напишете програма hunterxhunter која ќе ја најде најдобрата сума која би ја добиле за дадени податоци.
Во првиот ред има 2 ненегативни цели броеви: и — бројот на натпреварувачи, и бројот на поени кои се доделуваат за „убавите" беџови (за сопствениот беџ и за беџот на метата).
Во секој од следните реда има по 2 ненегативни цели броеви: T_i и L_i — метата на -тиот натпреварувач и бројот на денари кои би ги добиле ако тој натпреварувач премине на следно ниво.
На излез испечатете го максималниот број на денари кои би ги добиле.
Пример 1
Пример 2
Објаснување за тест пример 1
Натпреварувачите кои преминуваат на следното ниво се 1, 4 и 6. Еве една од можните ситуации: натпреварувачот со реден број 1 на крај ги има беџовите со број 1 и 6, тој со реден број 4 ги има беџовите 0, 4 и 7, а 6-тиот натпреварувач ги има беџовите 2, 3 и 5. Сумата на освоени денари е L_1 + L_4 + L_6 = 111 + 105 + 108 = 324.
За да ги добиете поените од подзадачата, мора да поминат сите тест примери од таа подзадача.
Подзадачите се следните:
Подзадача | Поени | Дополнителни ограничувања | |
1 | 10 | 10 | Нема |
2 | 15 | 700 | T_{P_j} = P_{(j+1) \bmod N} и L_{P_{N-1}} = 0 |
3 | 15 | 10^4 | T_{P_j} = P_{(j+1) \bmod N} и L_{P_{N-1}} = 0 |
4 | 10 | 700 | T_{P_j} = P_{(j+1) \bmod N} |
5 | 10 | 10^4 | T_{P_j} = P_{(j+1) \bmod N} |
6 | 20 | 700 | Нема |
7 | 20 | 10^4 | Нема |
Тука е произволна пермутација на броевите од 0 до N - 1 во која P_0 = 0.
Забелешка: (j + 1) \bmod N е остатокот од (j + 1) поделено со .
Ограничувања: