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

Король выяснил, что всего существует n драконов, для победы над i-ым из которых требуется армия из a_i солдат, причём в процессе сражения b_i из них будут убиты. Теперь он хотел бы определить, какое наименьшее количество солдат ему нужно собрать, чтобы убить всех драконов. Королю не принципиально, в каком порядке убивать этих драконов: главное, чтобы ни один из них не остался в живых.