Этикдўз

Этикдўзда $n$ та буюртма бор. $i$-буюртмани бажариш $T_i$ кун давом этади. Буюртма устида ишлаш бошланмагунча ҳар бир кечиккан кун учун $S_i$ сўм жарима тўланади: $i$-буюртма иши $C$-кун охирида бошланса (яъни ундан олдин $C$ кун бошқа буюртмалар билан ўтган бўлса), жарима $S_i \cdot C$.

Этикдўз бир вақтда фақат битта буюртма устида ишлайди ва буюртмаларни узлуксиз, кетма-кет бажаради. Жами жарима энг кичик бўладиган тартибни топинг. Бундай тартиблар бир нечта бўлса, буюртма рақамлари кетма-кетлиги лексикографик энг кичигини чиқаринг.

Биринчи қаторда $n$ ($1 \le n \le 10^5$). Кейинги $n$ та қаторда $T_i$ ва (). Буюртмалар дан гача рақамланган.

Биринчи қаторда энг кичик жами жарима. Иккинчи қаторда $n$ та сон — буюртмаларни бажариш тартиби.

Ёнма-ён турган $i$ ва $j$ буюртмаларнинг ўрнини алмаштириш фақат шу иккисининг жаримасини ўзгартиради: $i$ олдин бўлса ортиқча жарима $T_i S_j$, олдин бўлса . Демак ни дан олдин қўйиш керак, агар бўлса ( — алмаштириш усули). Нисбатларни каср кўринишида солиштирманг — кўпайтмаларни солиштириш аниқ. Тенг бўлса, рақами кичиги олдин.