У Раджа есть одна физическая сетевая линия, которая соединяет его офис с интернетом. Пропускная способность этой линии составляет \(b\) байт в миллисекунду.
Есть \(n\) пользователей, которые хотели бы использовать эту сетевую линию для передачи некоторых данных. \(i\)-й из них будет использовать линию начиная с миллисекунды \(s_i\) и до миллисекунды \(f_i\) включительно. Изначально он установит свою скорость передачи данных в значение \(d_i\). Это означает, что он будет использовать скорость передачи данных, равную \(d_i\), в течение миллисекунды \(s_i\), а затем она будет меняться в соответствии с процедурой, описанной ниже.
Контроль за соблюдением пропускной способности линии происходит следующим образом. Предположим, что есть \(m\) пользователей, пытающихся передать какие-то данные по заданной сетевой линии в течение миллисекунды \(x\). Обозначим за \(t_i\) скорость передачи данных у \(i\)-м из этих \(m\) пользователей в начале данной миллисекунды. Все \(t_i\) являются целыми неотрицательными значениями.
- Если \(m = 0\), то есть в течение этой миллисекунды нет пользователей, пытающихся передать данные, ничего не происходит.
- Если сумма всех \(t_i\) меньше или равна \(b\), то каждый активный пользователь успешно завершает свою передачу данных (\(i\)-й активный пользователь передаёт \(t_i\) байт). После этого скорость передачи данных каждого активного пользователя увеличивается на \(1\), то есть каждое \(t_i\) увеличивается на \(1\).
- Если сумма всех \(t_i\) больше, чем \(b\), то возникает перегрузка линии и в эту миллисекунду вообще никому не удаётся передать данные. В таком случае каждое значение \(t_i\) уменьшается вдвое, то есть каждое \(t_i\) заменяется на \(\lfloor \frac{t_i}{2} \rfloor\).
Радж знает все значения \(n\), \(b\), \(s_i\), \(f_i\) и \(d_i\), он хочет подсчитать общее количество байтов, переданных всеми пользователями в совокупности.
Примечание
Рассмотрим первый пример.
- Миллисекунда \(1\): Пользователь \(1\) передает \(2\) байта.
- Миллисекунда \(2\): Пользователь \(1\) передает \(3\) байта.
- Миллисекунда \(3\): Возникает перегрузка, и никто не передает данные.
- Миллисекунда \(4\): Пользователь \(1\) передает \(2\) байта.
- Миллисекунда \(5\): Пользователь \(1\) передает \(3\) байта.
Во втором примере в каждую миллисекунду с \(7\)-й по \(11\)-ю включительно возникает перегрузка, и единственный пользователь уменьшает свою скорость вдвое. Однако он не успевает достаточно снизить скорость до отключения.
Рассмотрим третий пример.
- Миллисекунда \(1\): Пользователь \(1\) передает \(1\) байт.
- Миллисекунда \(2\): Пользователь \(1\) передает \(2\) байта.
- Миллисекунда \(3\): Пользователь \(1\) передает \(3\) байта.
- Миллисекунда \(4\): Пользователь \(1\) передает \(4\) байта.
- Миллисекунда \(5\): Пользователь \(1\) передает \(5\) байтов.
- Миллисекунда \(6\): Пользователь \(1\) передает \(6\) байтов.
- Миллисекунда \(7\): Возникает перегрузка, и никто не передает данные.
- Миллисекунда \(8\): Пользователь \(1\) передает \(3\) байта. Пользователь \(2\) передает \(3\) байта.
- Миллисекунда \(9\): Возникает перегрузка, и никто не передает данные.
- Миллисекунда \(10\): Пользователь \(1\) передает \(2\) байта. Пользователь \(2\) передает \(2\) байта.
- Миллисекунда \(11\): Пользователь \(1\) передает \(3\) байта. Пользователь \(2\) передает \(3\) байта.
- Миллисекунда \(12\): Возникает перегрузка, и никто не передает данные.
- Миллисекунда \(13\): Пользователь \(2\) передает \(2\) байта.
- Миллисекунда \(14\): Пользователь \(2\) передает \(3\) байта.
- Миллисекунда \(15\): Пользователь \(2\) передает \(4\) байта.
- Миллисекунда \(16\): Пользователь \(2\) передает \(5\) байтов.
- Миллисекунда \(17\): Пользователь \(2\) передает \(6\) байтов.
- Миллисекунда \(18\): Возникает перегрузка, и никто не передает данные.
- Миллисекунда \(19\): Пользователь \(2\) передает \(3\) байта.
- Миллисекунда \(20\): Пользователь \(2\) передает \(4\) байта.