Задача . G. Повар и каша

Наконец-то, обед!

\(n\) школьников выстроились в длинную очередь к палатке повара за кашей. Повар будет выдавать кашу в течение \(D\) минут. Школьник, который стоит на \(i\)-м месте в очереди, имеет приоритет \(k_i\) и съедает одну порцию каши за \(s_i\) минут.

В начале каждой минуты перерыва повар накладывает первому в очереди школьнику одну порцию каши, после этого школьник уходит есть свою порцию. Если \(i\)-му школьнику выдали порцию в начале \(x\)-й минуты, то он вернётся в очередь в конце \((x + s_i)\)-й минуты.

Когда \(i\)-й школьник возвращается в очередь, школьники в конце очереди, приоритет которых строго меньше, чем у \(i\)-го школьника, должны пропустить его. Таким образом, он встанет в очередь за последним из школьников, приоритет которого не меньше, чем его собственный. То есть за последним школьником \(j\), у которого \(k_j \ge k_i\). Если в очереди нет ни одного такого школьника, то \(i\)-й школьник встаёт в начало очереди.

Если несколько школьников возвращаются в одно время, то они вернутся в очередь в порядке возрастания их \(s_i\).

Например, если \(n = 3\), \(D = 3\), \(k = [2, 3, 2]\) и \(s = [2, 1, 3]\), то выдача будет происходить следующим образом:

• В начале \(1\) минуты в очереди стоят школьники \([1, 2, 3]\), школьнику \(1\) выдают кашу;
• в начале \(2\) минуты в очереди стоят школьники \([2, 3]\), школьнику \(2\) выдают кашу;
• в начале \(3\) минуты в очереди стоят школьники \([3]\) школьнику \(3\) выдают кашу;
• в конце \(3\) минуты в очередь возвращается школьник \(2\) и очередь становится \([2]\);
• в конце \(3\) минуты в очередь возвращается школьник \(1\) и очередь становится \([2, 1]\), так как его приоритет ниже.

Определите, через какое минимальное количество минут после начала перерыва каждый школьник получит кашу хотя бы один раз или сообщите, что за \(D\) минут этого не произойдёт.