paginate_links and query vars

I have using the WordPress paginate_links() to build a paginator on a custom archive template for a custom post type. My site uses permalinks:

<?php echo paginate_links(array(
    'base' => get_pagenum_link(1) . '%_%',
    'current' => max(1, get_query_var('paged')),
    'format' => 'page/%#%',
    'total' => $wp_query->max_num_pages,
)); ?>

This works fine until I try to add query string vars to build a custom search string when the paginator echoes:

.../entries?post_type=entry&s=testpage/1
.../entries?post_type=entry&s=testpage/2

Instead of:

.../entries/page/1?post_type=entry&s=test
.../entries/page/2?post_type=entry&s=test

and so on… How can I get the correctly formatted URLs?

Seems that the query string is coming from the base argument call to get_pagenum_link() so I have removed the query string component and re-add it with ‘add_args’. Like so:

<?php echo paginate_links(array(
     'base' => preg_replace('/\?.*/', "https://wordpress.stackexchange.com/", get_pagenum_link(1)) . '%_%',
     'current' => max(1, get_query_var('paged')),
     'format' => 'page/%#%',
     'total' => $wp_query->max_num_pages,
     'add_args' => array(
         's' => get_query_var('s'),
         'post_type' => get_query_var('post_type'),
     )
 )); ?>