problem

There are many near toyosaki School Park n n n stores, at the moment 0 0 At 0:00, Yingli started shopping from the school park.

It takes time to walk from the school park to any store, or from one store to another 1 1 1 unit time.

If Yingli is at the moment t t t arrived at the store i i i. She needs to spend first a i × t + b i a_i × t + b_i ai​ × Queuing time of t+bi +,
Then you can buy the goods in this store.

Yingli wants to know at the moment T + 0.5 T + 0.5 How many different stores can she buy at most before T+0.5?

It is assumed here that it will only consume time on walking and queuing, and it will not consume time to buy items.

n ≤ 1 e 7 , T ≤ 1 e 9 n\le 1e7,T\le 1e9 n≤1e7,T≤1e9.

solution

Suppose in t t Ttime selection i i i shop to buy, and then go immediately j j j store purchase, then j j j the store will pay more ( a i ⋅ t + b i + 1 ) ⋅ a j (a_i·t+b_i+1)·a_j (ai ⋅ t+bi + 1) ⋅ aj.

Suppose in t t Ttime selection j j j shop to buy, and then go immediately i i i store purchase, then i i i the store will pay more ( a j ⋅ t + b j + 1 ) ⋅ a i (a_j·t+b_j+1)·a_i (aj ⋅ t+bj + 1) ⋅ ai.

If you choose first i i After i j j The order of j shall be met ( a i ⋅ t + b i + 1 ) ⋅ a j < ( a j ⋅ t + b j + 1 ) ⋅ a i ⇒ ( b i + 1 ) ⋅ a j < ( b j + 1 ) ⋅ a i (a_i·t+b_i+1)·a_j<(a_j·t+b_j+1)·a_i\Rightarrow (b_i+1)·a_j<(b_j+1)·a_i (ai​⋅t+bi​+1)⋅aj​<(aj​⋅t+bj​+1)⋅ai​⇒(bi​+1)⋅aj​<(bj​+1)⋅ai​.

Order and time of store discovery t t t is irrelevant.

Therefore, stores can be sorted according to this relationship.

Finally, the order of actually going to stores is sorted according to time, which must be a sub sequence of the new sequence formed after sorting according to this relationship.

Set up violently d p i , j : dp_{i,j}: dpi,j: after traversing to i i i store (sorted), in j j The minimum time it takes for j stores to buy goods, and whether to enter or not is considered i i i store, time complexity O ( n 2 ) O(n^2) O(n2).

Consider special data points ∀ i   a i > 0 \forall_i\ a_i>0 ∀i​ ai​>0.

Through the time transfer formula, it can be found that if a i ≠ 0 a_i\neq 0 ai  = 0, then the time after entering the store increases exponentially.

This means that the second place of the transfer only needs to drive to log ⁡ T \log T The logT level is OK.

In fact, this is almost a positive solution.

Will all a i = 0 a_i=0 Stores with ai = 0 rank last, only considering a i ≠ 0 a_i\neq 0 For stores with ai  = 0, follow the optimized above d p dp dp can do it.

Finally, consider the remaining time T − d p k , i T-dp_{k,i} How many can be connected after T − dpk,i a i = 0 a_i=0 Stores with ai = 0, greedily set these special stores according to b b b sort in ascending order.

Time complexity: O ( n log ⁡ n + n log ⁡ T ) O(n\log n+n\log T) O(nlogn+nlogT).

code

#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
#define maxn 200005
struct node { int a, b; }it[maxn];
int n, m, T, k;
int dp[maxn][35];

void read( int &x ) {
    x = 0; char s = getchar();
    while( s < '0' or s > '9' ) s = getchar();
    while( '0' <= s and s <= '9' ) x = ( x << 1 ) + ( x << 3 ) + ( s ^ 48 ), s = getchar();
}

signed main() {
    freopen( "eriri.in", "r", stdin );
    freopen( "eriri.out", "w", stdout );
    read( n ), read( T );
    m = log( T ) / log( 2 );
    for( int i = 1;i <= n;i ++ ) read( it[i].a ), read( it[i].b );
    sort( it + 1, it + n + 1, []( node x, node y ) { return ( x.b + 1 ) * y.a < ( y.b + 1 ) * x.a; } );
    while( it[k + 1].a ) k ++;
    for( int i = 0;i <= n;i ++ )
        for( int j = 1;j <= m;j ++ ) dp[i][j] = T + 1;
    for( int i = 1;i <= k;i ++ )
        for( int j = 1;j <= m;j ++ )
            dp[i][j] = min( min( T + 1, dp[i - 1][j] ), dp[i - 1][j - 1] + 1 + ( dp[i - 1][j - 1] + 1 ) * it[i].a + it[i].b );
    sort( it + k + 1, it + n + 1, []( node x, node y ) { return x.b < y.b; } );
    int ans = 0;
    for( int i = 0;i <= m and dp[k][i] <= T;i ++ ) {
        int sum = T - dp[k][i], cnt = 0;
        for( int j = k + 1;j <= n and sum > it[j].b;j ++ )
            cnt ++, sum -= it[j].b + 1;
        ans = max( ans, i + cnt );
    }
    printf( "%lld\n", ans );
    return 0;
}